原题
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例：
输入: [10,9,2,5,3,7,101,18] 输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明：
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
解法
思想
动态规划，对于某个元素，其dp值应该等于左边比其小的元素中最大的dp值+1。
代码
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length];
dp[0] = 1;
int maxCount = 1;
for (int i = 1; i < dp.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) maxval = Math.max(maxval, dp[j]);
}
dp[i] = maxval + 1;
maxCount = Math.max(maxCount, dp[i]);
}
return maxCount;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode300-%e6%9c%80%e9%95%bf%e4%b8%8a%e5%8d%87%e5%ad%90%e5%ba%8f%e5%88%97/
