397. Longest Continuous Increasing Subsequence

题目

给定一个整数数组(下标从 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;
    }
}
Show Comments

Get the latest posts delivered right to your inbox.