Longest Increasing Continuous subsequence

Give you an integer array (index from 0 to n-1, where n is the size of this array)，find the longest increasing continuous subsequence in this array. (The definition of the longest increasing continuous subsequence here can be from right to left or from left to right)

http://www.lintcode.com/en/problem/longest-increasing-continuous-subsequence/

Solution 1

判断连续递增的subsequence的长度，递减的同样的方法。

class Solution {
public:
    /**
     * @param A an array of Integer
     * @return  an integer
     */
    int longestIncreasingContinuousSubsequence(vector<int>& A) {
        // Write your code here
        if(A.size() == 0) return 0;
        int case1 = helper(A);
        reverse(A.begin(), A.end());
        int case2 = helper(A);
        return max(case1, case2);
    }
    int helper(vector<int> &A) {
        int result = 1;
        int n = A.size();
        int pre = A[0];
        int local  = 1;
        for(int i=1; i<A.size(); i++) {
            if(A[i]> pre) {
                local++;
            } else {
                local = 1;
            }
            pre = A[i];
            result = max(result, local);
        }
        return result;
    }
};

一个for loop的写法：

// Time:  O(n)
// Space: O(1)

class Solution {
public:
    /**
     * @param A an array of Integer
     * @return  an integer
     */
    int longestIncreasingContinuousSubsequence(vector<int>& A) {
        int max_inc_len = 0, cur_inc_len = 0;
        int max_dec_len = 0, cur_dec_len = 0;

        for (int i = 0; i < A.size(); ++i) {
            if (i == 0 || A[i] == A[i - 1]) {
                max_inc_len = max(max_inc_len, ++cur_inc_len);
                max_dec_len = max(max_dec_len, ++cur_dec_len);
            } else if (A[i] > A[i - 1]) {
                max_inc_len = max(max_inc_len, ++cur_inc_len);
                cur_dec_len = 1;
            } else if (A[i] < A[i - 1]) {
                max_dec_len = max(max_dec_len, ++cur_dec_len);
                cur_inc_len = 1;
            }
        }

        return max(max_inc_len, max_dec_len);
    }
};

DP。相应的状态dp[i]即为从索引 i 出发所能得到的最长连续递增子序列。