最长递增子序列java
时间: 2023-10-14 20:14:09 浏览: 50
下面是一个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实现最长递增子序列的例子。