题目描述
找出数组中非降序最长子数组
思路
DP。
dp[n]记录第i个元素位置处满足条件子数组的长度。
如果第i个元素大于等于第i-1个元素，
迭代公式：dp[i]=dp[i-1]+1
代码
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
| public class Main {
public static void main(String[] args){
int[] res = new Main().getIncreaseLen(new int[]{1,2,3,5,4,6,7,8,9});
for(int n : res) {
System.out.print(n);
}
}
public int[] getIncreaseLen(int[] num) {
int n = num.length;
int[] dp = new int[n];
dp[0] = 1;
int max = 1; // 最长非降序个数
int index = 0; // 指向最长非降序子数组的末尾
for(int i = 1; i < num.length; i++) {
if(num[i] >= num[i-1]) {
dp[i] = dp[i-1] + 1;
if(dp[i] > max) {
max = dp[i];
index = i;
}
}else {
dp[i] = 1;
}
}
int[] res = new int[max];
for(int j = 0; j < max; j++) {
res[j] = num[index-max+1+j];
}
return res;
}
}
|
考察点