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