最长上升连续子序列

题意

给定一个整数数组(下标从 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.

思路

max 存储最大的上升连续子序列
count 记录可能为最大循环子序列的统计
先从左侧开始循环,若当前数大于下一个数,那么 count++,如果 count > max,则将 count 赋值给 max。然后从右侧向左开始循环,同理。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
/*
* @param : An array of Integer
* @return: an integer
*/
public int longestIncreasingContinuousSubsequence(int[] A) {
if (A == null || A.length == 0) {
return 0;
}

int max = 1;
int count = 1;
for (int i = 0; i < A.length - 1; i++) {
if (A[i] < A[i + 1]) {
count++;
} else {
count = 1;
}
max = count > max ? count : max;
}

count = 1;

for (int i = A.length-1; i > 0; i--) {
if (A[i] < A[i - 1]) {
count++;
} else {
count = 1;
}
max = count > max ? count : max;
}

return max;
}
}

原题地址

LintCode:最长上升连续子序列