题目

给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。（最长上升连续子序列可以定义为从右到左或从左到右的序列。）

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

分析

虽然叫上升序列，但其实升、降都可以，具体的差值不用关心，只要描述出增长的趋势就可以了。

因此，可以先将原始数组做一遍处理，计算出相邻两个元素的差值，产生一个新数组，由于不必关心实际数值，新数组中，可以使用1或-1来表示相邻的大小关系，至于相等的元素，都应当忽略。

这样一来，我们就会得到一个完全由1或-1组成的序列，计算连续的相同数字个数，取最大值，就是我们要求的连续增长子序列的大小。

代码

public class Solution {
    
    
    List merge(List A){
        List result = new ArrayList<>();
        int total = 1;
        for(int i=1; i < A.size() ; i++) {
            if (A.get(i-1).intValue() != A.get(i).intValue()) {
                result.add(total);
                total = 1;
            } else {
                total++;
            }
        }
        result.add(total);
        return result;
    }
    
    List normalize(int[] A) {
        List r = new ArrayList<>();
        
        for(int i = 1; i < A.length; i++) {
            if (A[i - 1] > A[i]) {
                r.add(-1);
            } else if (A[i-1] < A[i]) {
                r.add(1);
            } else {
                continue;
            }
        }
        return r;
    }
    /**
     * @param A: An array of Integer
     * @return: an integer
     */
    public int longestIncreasingContinuousSubsequence(int[] A) {
        // write your code here
        if (A == null || A.length == 0) return 0;
        if (A.length == 1) return 1;
        
        List n = normalize(A);
        List r = merge(n);
        
        int total = r.get(0).intValue();
        
        for(int i = 1; i < r.size() ; i++) {
            if( total < r.get(i).intValue() ) {
                total = r.get(i).intValue();
            }
        }
        return total + 1;
    }
}