最长增长子序列
给定一个数组arr，返回arr的最长增长子序列，例，arr = {7,1,9,3,8,19},最长增长子序列为 {1,3,8,19}。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public static int[] generateLIS (int[] arr,int[] dp) {
int len = 0;
int index = 0;
for (int i = 0;i < dp.length;i ++) {
if (dp[i] > len) {
len = dp[i];
index = i;
}
}
int[] lis = new int[len];
lis[--len] = arr[index];
for (int i = index;i >= 0;i--) {
if (arr[i] < arr[index] && dp[i] == dp[index] - 1) {
lis[--len] = arr[i];
index = i;
}
}
return lis;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| public static int[] getdp1 (int[] arr) {
int[] dp = new int[arr.length];
for (int i = 0;i < arr.length;i++) {
dp[i] = 1;
for (int j = 0;j < i;j++) {
if (arr[i] > arr[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return dp;
}
|