构造最长递增子序列java
时间: 2023-10-14 22:27:35 浏览: 39
最长递增子序列(Longest Increasing Subsequence,简称 LIS)是指在一个序列中,找到一个尽可能长的子序列满足单调递增。以下是 Java 实现:
```java
public static int lis(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
```
其中,`dp[i]` 表示以 `nums[i]` 结尾的最长递增子序列的长度。我们可以从前向后遍历数组,依次计算出 `dp[i]` 的值。对于每个 `i`,我们再从 `0` 到 `i-1` 遍历一次,找到所有比 `nums[i]` 小的数,并更新 `dp[i]` 的值。最后,我们返回 `dp` 数组中的最大值即可。
相关问题
最长递增子序列java
下面是一个Java实现最长递增子序列的例子:
```java
public class LongestIncreasingSubsequence {
public static int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int res = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
public static void main(String[] args) {
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println(lengthOfLIS(nums)); // expected output: 4
}
}
```
在这个例子中,使用动态规划的方法来解决最长递增子序列问题。使用一个一维数组 `dp` 来记录每个位置的最长递增子序列长度。初始时,所有位置的最长递增子序列长度都为1。接着,使用两重循环来遍历所有可能的子序列,如果发现一个数字比前面的数字大,那么就可以把前面的数字加入到当前数字的最长递增子序列中,更新 `dp` 数组的值。最后,返回 `dp` 数组中的最大值即可。
以上就是一个简单的Java实现最长递增子序列的例子。
输出最长递增子序列java
以下是一个简单的Java代码,用于找到最长递增子序列:
```java
import java.util.*;
public class LongestIncreasingSubsequence {
// 返回最长递增子序列的长度
static int longestIncreasingSubsequence(int[] arr, int n) {
int[] lis = new int[n];
int i, j, max = 0;
// 初始化LIS值为1
for (i = 0; i < n; i++)
lis[i] = 1;
// 计算LIS值
for (i = 1; i < n; i++)
for (j = 0; j < i; j++)
if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
// 找到最大的LIS值
for (i = 0; i < n; i++)
if (max < lis[i])
max = lis[i];
return max;
}
public static void main(String args[]) {
int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
int n = arr.length;
System.out.println("Length of Longest Increasing Subsequence is " + longestIncreasingSubsequence(arr, n));
}
}
```
输出:
```
Length of Longest Increasing Subsequence is 5
```
上面的代码使用了动态规划技术来计算最长递增子序列。它首先初始化一个数组lis,将所有元素的LIS值设置为1。然后它遍历数组,计算LIS值。最后,它找到最大的LIS值并返回它。