題目

給定一個(gè)整數(shù)數(shù)組（下標(biāo)從 0 到 n-1十拣， n 表示整個(gè)數(shù)組的規(guī)模）祭饭，請(qǐng)找出該數(shù)組中的最長(zhǎng)上升連續(xù)子序列图毕。（最長(zhǎng)上升連續(xù)子序列可以定義為從右到左或從左到右的序列惫皱。）

樣例

給定 [5, 4, 2, 1, 3], 其最長(zhǎng)上升連續(xù)子序列（LICS）為 [5, 4, 2, 1], 返回 4.
給定 [5, 1, 2, 3, 4], 其最長(zhǎng)上升連續(xù)子序列（LICS）為 [1, 2, 3, 4], 返回 4.

分析1（普通解法）

最簡(jiǎn)單的思路像樊，遍歷兩遍，正向和反向各一遍旅敷，利用兩個(gè)變量記錄最長(zhǎng)序列的長(zhǎng)度生棍。具體閱讀代碼，就可以知道媳谁。

public class Solution {
    /**
     * @param A an array of Integer
     * @return  an integer
     */
    public int longestIncreasingContinuousSubsequence(int[] A) {
        // Write your code here
        int max=1,count=1;
        if(A.length == 0)
            return A.length;
        for(int i=1;i<A.length;i++)
        {
            while(i<A.length && A[i-1]<A[i])
            {
                i++;
                count++;
            }
            if(count>max)
                max=count;
            else
                count=1;
            count=1;
        }
        
        for(int i=A.length-1;i>0;i--)
        {
            while(i>0 && A[i-1]>A[i])
            {
                i--;
                count++;
            }
            if(count>max)
                max=count;
            else
                count=1;
            count=1;
        }
        
        return max;
    }
}

時(shí)間復(fù)雜度遍歷了數(shù)組兩次涂滴，較慢

分析2（使用隊(duì)列）

引入隊(duì)列可以是思路更清晰友酱，而且我們只要遍歷一遍就可以了
原理是：首先將第一個(gè)元素進(jìn)隊(duì)，然后循環(huán)將后面的元素進(jìn)隊(duì)柔纵，如果是遞增的缔杉，就直接進(jìn)隊(duì)，直到碰到不是遞增的搁料，記錄下此時(shí)隊(duì)列的大小或详，隊(duì)列的大小就是這個(gè)遞增序列的長(zhǎng)度，然后清空隊(duì)列加缘，繼續(xù)進(jìn)隊(duì)鸭叙，重復(fù)這個(gè)過程，最后留下來(lái)的就是最長(zhǎng)遞增序列的長(zhǎng)度拣宏。

public class Solution {
    /**
     * @param A an array of Integer
     * @return  an integer
     */
    public int longestIncreasingContinuousSubsequence(int[] A) {
        // Write your code here
        if(A.length == 0)
            return 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(A[0]);
        int max=1,count=1;
        for(int i=1;i<A.length;i++)
        {
            if(A[i]<A[i-1])
            {
                count = queue.size();
                if(count>max)
                    max = count;
                queue.clear();
            }
            queue.offer(A[i]);
        }
        count = queue.size();
        if(count>max)
            max = count;
        
        queue.clear();
        
        queue.offer(A[A.length-1]);
        for(int i=A.length-1;i>0;i--)
        {
            if(A[i]>A[i-1])
            {
                count = queue.size();
                if(count>max)
                    max = count;
                queue.clear();
            }
            queue.offer(A[i]);
        }
        
        count = queue.size();
        if(count>max)
            max = count;
        
        return max;
    }
}