题目链接
题目描述
实现代码
动态规划思想:记dp[i]表示数组nums的前i个数组成的子数组的最长递增子序列长度,因此有状态转移方程:
dp[i] = max(dp[x] + (nums[i] > nums[x] ? 1 : 0) ), 0 < x < i
可以看看官方题解给的动图:动图链接
实现代码:
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}