给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续子序列。(最长上升连续子序列可以定义为从右到左或从左到右的序列。)
样例给定 [5, 4, 2, 1, 3], 其最长上升连续子序列(LICS)为 [5, 4, 2, 1], 返回 4.
给定 [5, 1, 2, 3, 4], 其最长上升连续子序列(LICS)为 [1, 2, 3, 4], 返回 4.
思路:
遍历一遍数组,找出最大的升序降序长度即可。
代码:
public int longestIncreasingContinuousSubsequence(int[] A) { // Write your code here int len = A.length; int a=0,b=0;//最大的递增、递减长度 int p=1,q=1; // 递增(减)序列的长度临时变量 if(len==1) return 1;// 数组长度为1,直接返回1; for(int i=0 ; i<len-1 ; i++){ if(A[i]-A[i+1]<0){ //如果是递增 q=1;//把递减序列临时变量长度置为1,递减序列重新开始计数 p++;//递增序列长度加1 if(p>a) a=p; } else{ p=1; q++; if(q>b) b=q; } } return Math.abs(a)>Math.abs(b)?a:b;//返回两个长度绝对值的大的一方 }