构造最长递增子序列java
时间: 2023-10-14 15:14:10 浏览: 38
最长递增子序列问题可以使用动态规划算法来解决。以下是Java实现:
```java
public static int[] getLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int[] pre = new int[n];
int len = 0, idx = 0;
Arrays.fill(pre, -1);
for (int i = 0; i < n; i++) {
int j = Arrays.binarySearch(dp, 0, len, nums[i]);
if (j < 0) {
j = -(j + 1);
}
dp[j] = nums[i];
if (j == len) {
len++;
idx = i;
}
if (j > 0) {
pre[i] = idx;
}
}
int[] lis = new int[len];
for (int i = idx, j = len - 1; i >= 0; i--) {
if (dp[j] == nums[i]) {
lis[j--] = nums[i];
idx = i;
}
}
return lis;
}
```
该算法使用了一个dp数组来维护当前已知的最长递增子序列,以及一个pre数组来记录每个数的前驱。在遍历数组时,如果当前数比已知最长递增子序列中的最后一个数还大,则将该数加入到dp数组中;否则,找到dp数组中第一个比该数大的数并替换它。同时记录下该数的前驱,便于后面构造最长递增子序列。
最后,从最后一个数开始,根据其前驱依次向前构造出最长递增子序列。