久久精品中文字幕av,av.涩涩涩涩涩涩涩涩,亚洲国产日韩欧美精品成人久久久,成人福利电影免费在线观看,日产国产原创av,日韩av午夜激情,bt天堂中文字幕,超级碰人妻在线视频,欧美老熟妇久久一区二区

# 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 題目只要返回最大長(zhǎng)度，注意此題中的連續(xù)遞增指的是雙向的，即可遞增也可遞減。簡(jiǎn)單點(diǎn)考慮可分兩種情況，一種遞增，另一種遞減，跟蹤最大遞增長(zhǎng)度，最后返回即可。也可以在一個(gè) for 循環(huán)中搞定，只不過(guò)需要增加一布爾變量判斷之前是遞增還是遞減。 ### 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; } } ~~~ ### 源碼分析 使用兩個(gè) for 循環(huán)時(shí)容易在第二次循環(huán)忘記重置。使用一個(gè) for 循環(huán)時(shí)使用下標(biāo)來(lái)計(jì)數(shù)較為方便。 ### 復(fù)雜度分析 時(shí)間復(fù)雜度 O(n)O(n)O(n), 空間復(fù)雜度 O(1)O(1)O(1). ### 題解2 - 動(dòng)態(tài)規(guī)劃 除了題解1 中分兩種情況討論外，我們還可以使用動(dòng)態(tài)規(guī)劃求解。狀態(tài)轉(zhuǎn)移方程容易得到——要么向右增長(zhǎng)，要么向左增長(zhǎng)。相應(yīng)的狀態(tài)`dp[i]`即為從索引 i 出發(fā)所能得到的最長(zhǎng)連續(xù)遞增子序列。這樣就避免了分兩個(gè)循環(huán)處理了，這種思想對(duì)此題的 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, 深度優(yōu)先搜索") 中使用記憶化存儲(chǔ)避免重復(fù)遞歸，分左右兩個(gè)方向遞增，最后取較大值。這種方法對(duì)于數(shù)組長(zhǎng)度較長(zhǎng)時(shí)棧會(huì)溢出。 ### 復(fù)雜度分析 時(shí)間復(fù)雜度 O(n)O(n)O(n), 空間復(fù)雜度 (n)(n)(n). ### Reference - [Lintcode: Longest Increasing Continuous subsequence | codesolutiony](https://codesolutiony.wordpress.com/2015/05/25/lintcode-longest-increasing-continuous-subsequence/)