leetcode hot 100-300. 最长上升子序列

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

思路一：动态规划

思路参考：动态规划 ---- 最长不下降子序列（Longest Increasing Sequence, LIS）

dp[i]表示以nums[i]为结尾的最长上升子序列的长度

计算dp[i]的过程为，遍历[0, i-1]之间的元素 nums[j] ，判断能否把 nums[i] 加入到以 nums[j] 元素结尾的最长上升子序列的尾部，加入依据是仍然维持是一个上升子序列。即判断是否 nums[i] > nums[j]

如果可以则判断能否能把 dp[i] 增大，即能否比 nums[i] 当前所在的最长上升子序列长度更长，如果可以（即如果 dp[j] + 1 > dp[i]），把nums[i]元素加入到 nums[j] 所在的上升子序列中，则dp[i] = dp[j] + 1

边界情况分析，每个元素都可以以当前元素为一个上升子序列，所以显然每个 dp[i] 最小为1，所以dp[i]的初值为 1

 1 class Solution {
 2     public int lengthOfLIS(int[] nums) {
 3         if(nums == null || nums.length == 0){
 4             return 0;
 5         }
 6 
 7         // 边界情况分析，每个元素都可以以当前元素为一个上升子序列，所以显然每个dp[i]最小为1
 8         int len = nums.length;
 9         int[] dp = new int[len];
10         int max = 1;
11         dp[0] = 1;
12         for(int i = 1; i < len; i++){
13             dp[i] = 1;
14             for(int j = 0; j < i; j++){
15                     // 如果可以维持一个上升序列且时最长上升序列更长，则更新dp[i]
16                     if(nums[i] > nums[j] && dp[j] + 1 > dp[i]){
17                     dp[i] = dp[j] + 1;
18                 }
19             }
20             max = Math.max(dp[i], max);
21         }
22         return max;
23     }
24 }

leetcode 执行用时：15 ms > 44.16%, 内存消耗：36.3 MB > 95.15%

复杂度分析：

时间复杂度：O(n²)。双循环，所以时间复杂度为O(n²)。

空间复杂度：O(n)。需要一个大小为 n 辅助数组dp[], 所以空间复杂度为O(n)。