[LintCode] Longest Increasing Continuous Subseque

wwq0327 發布于2019-08-14 15:11 / 481人閱讀

摘要：最長連續遞增遞減子序列，設置正向計數器，后一位增加則計數器加，否則置。反向計數器亦然。每一次比較后將較大值存入。

Problem 最長連續遞增／遞減子序列

Give an integer array，find the longest increasing continuous subsequence in this array.
An increasing continuous subsequence:
Can be from right to left or from left to right.
Indices of the integers in the subsequence should be continuous.

Example

For [5, 4, 2, 1, 3], the LICS is [5, 4, 2, 1], return 4.
For [5, 1, 2, 3, 4], the LICS is [1, 2, 3, 4], return 4.

Note

設置正向計數器，后一位增加則計數器加1，否則置1。反向計數器亦然。
每一次比較后將較大值存入max。

Solution

O(1) space, O(n) time

public class Solution {
    public int longestIncreasingContinuousSubsequence(int[] A) {
        if (A == null || A.length == 0) return 0;
        int n = A.length;
        int count = 1, countn = 1, max = 1;
        int i = 1;
        while (i != n) {
            if (A[i] >= A[i-1]) {
                count++;
                countn = 1;
                max = Math.max(max, count);
            }
            else {
                countn++;
                count = 1;
                max = Math.max(max, countn);
            }
            i++;
        }
        return max;
    }
}

DP using two dp arrays, O(n) space

public class Solution {
    public int longestIncreasingContinuousSubsequence(int[] A) {
        if (A == null || A.length == 0) return 0;
        int n = A.length;
        if (n == 1) return 1;
        int[] dp = new int[n];
        int[] pd = new int[n];
        int maxdp = 0, maxpd = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = A[i] >= A[i-1] ? dp[i-1]+1 : 1;
            maxdp = Math.max(maxdp, dp[i]);
        }
        pd[n-1] = 1;
        for (int i = n-2; i >= 0; i--) {
            pd[i] = A[i] >= A[i+1] ? pd[i+1]+1 : 1;
            maxpd = Math.max(maxpd, pd[i]);
        }
        return Math.max(maxdp, maxpd);
    }
}

DP using one dp arrays, O(n) space

public class Solution {
    public int longestIncreasingContinuousSubsequence(int[] A) {
        if (A == null || A.length == 0) return 0;
        int n = A.length;
        if (n == 1) return 1;
        int[] dp = new int[n];
        int maxdp = 0, maxpd = 0;
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = A[i] >= A[i-1] ? dp[i-1]+1 : 1;
            maxdp = Math.max(maxdp, dp[i]);
        }
        for (int i = 1; i < n; i++) {
            dp[i] = A[i] <= A[i-1] ? dp[i-1]+1 : 1;
            maxpd = Math.max(maxpd, dp[i]);
        }
        return Math.max(maxdp, maxpd);
    }
}

GPU云服務器云服務器 Continuous Increasing Longest LintCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65419.html

[LintCode] Longest Increasing Subsequence

Problem Given a sequence of integers, find the longest increasing subsequence (LIS). You code should return the length of the LIS. Clarification Whats the definition of longest increasing subsequence?...

Flands 2019-08-14 14:22 評論0 收藏0
[Lintcode] Longest Increasing Subsequence 最長上升序列

摘要：樣例給出，這個是，返回給出，這個是，返回挑戰要求時間復雜度為或者說明最長上升子序列的定義最長上升子序列問題是在一個無序的給定序列中找到一個盡可能長的由低到高排列的子序列，這種子序列不一定是連續的或者唯一的。 Longest Increasing Subsequence 本文最新版本位于 https://yanjia.me/zh/2018/11/... 給定一個整數序列，找到最長上升子序...

hlcc 2019-08-14 12:41 評論0 收藏0
leetcode 329. Longest Increasing Path in a Matrix

摘要：題目要求思路和代碼這里采用廣度優先算法加上緩存的方式來實現。我們可以看到，以一個節點作為開始構成的最長路徑長度是確定的。因此我們可以充分利用之前得到的結論來減少重復遍歷的次數。題目要求 Given an integer matrix, find the length of the longest increasing path. From each cell, you can ei...

heartFollower 2019-08-16 11:09 評論0 收藏0
[LeetCode] 329. Longest Increasing Path in a Matri

Problem Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move ou...

hss01248 2019-08-16 13:25 評論0 收藏0
Longest Increasing Subsequence

摘要：解題思路求不必連續的最長升序字符串長度，采用動態規劃，利用狀態表示以字符結尾的最長子串的長度，那么狀態轉移方程就是且必須小于另外還需維護一個最大長度。 Longest Increasing SubsequenceGiven an unsorted array of integers, find the length of longest increasing subsequence. ...

yangrd 2019-08-16 10:27 評論0 收藏0