# Longest Increasing Continuous subsequence ### Source - lintcode: [(397) Longest Increasing Continuous subsequence](http://www.lintcode.com/en/problem/longest-increasing-continuous-subsequence/) ### Problem 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) #### 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 O(n) time and O(1) extra space. ### 題解1 題目只要返回最大長度，注意此題中的連續遞增指的是雙向的，即可遞增也可遞減。簡單點考慮可分兩種情況，一種遞增，另一種遞減，跟蹤最大遞增長度，最后返回即可。也可以在一個 for 循環中搞定，只不過需要增加一布爾變量判斷之前是遞增還是遞減。 ### Java - two for loop ~~~ public class Solution { /** * @param A an array of Integer * @return an integer */ public int longestIncreasingContinuousSubsequence(int[] A) { if (A == null || A.length == 0) return 0; int lics = 1, licsMax = 1, prev = A[0]; // ascending order for (int a : A) { lics = (prev < a) ? lics + 1 : 1; licsMax = Math.max(licsMax, lics); prev = a; } // reset lics = 1; prev = A[0]; // descending order for (int a : A) { lics = (prev > a) ? lics + 1 : 1; licsMax = Math.max(licsMax, lics); prev = a; } return licsMax; } } ~~~ ### Java - one for loop ~~~ public class Solution { /** * @param A an array of Integer * @return an integer */ public int longestIncreasingContinuousSubsequence(int[] A) { if (A == null || A.length == 0) return 0; int start = 0, licsMax = 1; boolean ascending = false; for (int i = 1; i < A.length; i++) { // ascending order if (A[i - 1] < A[i]) { if (!ascending) { ascending = true; start = i - 1; } } else if (A[i - 1] > A[i]) { // descending order if (ascending) { ascending = false; start = i - 1; } } else { start = i - 1; } licsMax = Math.max(licsMax, i - start + 1); } return licsMax; } } ~~~ ### 源碼分析 使用兩個 for 循環時容易在第二次循環忘記重置。使用一個 for 循環時使用下標來計數較為方便。 ### 復雜度分析 時間復雜度 O(n)O(n)O(n), 空間復雜度 O(1)O(1)O(1). ### 題解2 - 動態規劃 除了題解1 中分兩種情況討論外，我們還可以使用動態規劃求解。狀態轉移方程容易得到——要么向右增長，要么向左增長。相應的狀態`dp[i]`即為從索引 i 出發所能得到的最長連續遞增子序列。這樣就避免了分兩個循環處理了，這種思想對此題的 follow up 有特別大的幫助。 ### Java ~~~ public class Solution { /** * @param A an array of Integer * @return an integer */ public int longestIncreasingContinuousSubsequence(int[] A) { if (A == null || A.length == 0) return 0; int lics = 0; int[] dp = new int[A.length]; for (int i = 0; i < A.length; i++) { if (dp[i] == 0) { lics = Math.max(lics, dfs(A, i, dp)); } } return lics; } private int dfs(int[] A, int i, int[] dp) { if (dp[i] != 0) return dp[i]; // increasing from xxx to left, right int left = 0, right = 0; // increasing from right to left if (i > 0 && A[i - 1] > A[i]) left = dfs(A, i - 1, dp); // increasing from left to right if (i + 1 < A.length && A[i + 1] > A[i]) right = dfs(A, i + 1, dp); dp[i] = 1 + Math.max(left, right); return dp[i]; } } ~~~ ### 源碼分析 [dfs](# "Depth-First Search, 深度優先搜索") 中使用記憶化存儲避免重復遞歸，分左右兩個方向遞增，最后取較大值。這種方法對于數組長度較長時棧會溢出。 ### 復雜度分析 時間復雜度 O(n)O(n)O(n), 空間復雜度 (n)(n)(n). ### Reference - [Lintcode: Longest Increasing Continuous subsequence | codesolutiony](https://codesolutiony.wordpress.com/2015/05/25/lintcode-longest-increasing-continuous-subsequence/)