子序列和子数组 - 300. Longest Increasing Subsequence - 《LeetCode刷题》

Q: 一个无序数组中的最长递增子序列的长度
解决方法：动态规划
- 递推关系：
- 示例
最终代码
运行效率评价

Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Q: 一个无序数组中的最长递增子序列的长度

Constraints:

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

Example 1:

Input: nums = [10,9,2,5,3,7,101,18] 
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3] 
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7] 
Output: 1

解决方法：动态规划

定义数组DP，DP[i]表示以nums[i]为结尾元素的最长的递增子序列的长度。

递推关系：

当i=0时，显然DP[0]=1；
当i>0时，定义0<=jnums[j]，则DP[i]=DP[j]+1，也即以nums[i]为结尾元素的递增子序列是以nums[j]结尾的最长递增子序列再接上nums[i]；如果nums[i]<=nums[j]，则DP[i]=1，因为以nums[j]结尾的最长递增子序列如果接上nums[i]，则不构成递增序列，如果不接上nums[i]，令DP[i]=DP[j]，则不符合DP数组的定义，因此此时DP[i]=1，表示以nums[i]为结尾元素的递增子序列（即只有一个元素nums[i]）。而最终，nums[i]结尾的最长递增子序列则是所有的可能的递增序列中的最长的。

示例

以数组nums=[2,1,5,3,6,4,8,9,7]为例。

i=0时 | index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | nums[index] | 2 | 1 | 5 | 3 | 6 | 4 | 8 | 9 | 7 | | DP[index] | 1 | | | | | | | | |
i=1时
```
nums[1]=1, 1<2, 可能DP[1]=1;
        最终DP[1]=1
```
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | nums[index] | 2 | 1 | 5 | 3 | 6 | 4 | 8 | 9 | 7 | | DP[index] | 1 | 1 | | | | | | | |
i=2时
```
nums[2]=5, 5>1, 可能DP[2]=DP[1]+1=2;
        5>2, 可能DP[2]=DP[0]+1=2;
        最终DP[2]=2
```
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | nums[index] | 2 | 1 | 5 | 3 | 6 | 4 | 8 | 9 | 7 | | DP[index] | 1 | 1 | 2 | | | | | | |
i=3时
```
nums[3]=3, 3<5, 可能DP[3]=1;
        3>1, 可能DP[3]=DP[1]+1=2;
        3>2, 可能DP[3]=DP[0]+1=2;
        最终DP[3]=2
```
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | nums[index] | 2 | 1 | 5 | 3 | 6 | 4 | 8 | 9 | 7 | | DP[index] | 1 | 1 | 2 | 2 |
|
|
|
|
|
i=4时
```
nums[4]=6, 6>3, 可能DP[4]=DP[3]+1=3
        6>5, 可能DP[4]=DP[2]+1=3;
        6>1, 可能DP[4]=DP[1]+1=2;
        6>2, 可能DP[4]=DP[0]+1=2;
        最终DP[4]=3
```
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | nums[index] | 2 | 1 | 5 | 3 | 6 | 4 | 8 | 9 | 7 | | DP[index] | 1 | 1 | 2 | 2 | 3 |
|
|
|
|

i=5时

nums[5]=4, 4<6, 可能DP[5]=1;
        4>3, 可能DP[5]=DP[3]+1=3;
        4<5, 可能DP[5]=1;
        4>1, 可能DP[5]=DP[1]+1=2;
        4>2, 可能DP[5]=DP[0]+1=2;
        最终DP[5]=3

| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | nums[index] | 2 | 1 | 5 | 3 | 6 | 4 | 8 | 9 | 7 | | DP[index] | 1 | 1 | 2 | 2 | 3 | 3 |
|
|
|

i=6时

nums[6]=8, 8>4, 可能DP[6]=DP[5]+1=4;
        8>6, 可能DP[6]=DP[4]+1=4;
        8>3, 可能DP[6]=DP[3]+1=3;
        8>5, 可能DP[6]=DP[2]+1=3;
        8>1, 可能DP[6]=DP[1]+1=2;
        8>2, 可能DP[6]=DP[0]+1=2;
        最终DP[6]=4

| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | nums[index] | 2 | 1 | 5 | 3 | 6 | 4 | 8 | 9 | 7 | | DP[index] | 1 | 1 | 2 | 2 | 3 | 3 | 4 |
|
|

i=7时

nums[7]=9, 9>8, 可能DP[7]=DP[6]+1=5;
        9>4, 可能DP[7]=DP[5]+1=4;
        9>6, 可能DP[7]=DP[4]+1=4;
        9>3, 可能DP[7]=DP[3]+1=3;
        9>5, 可能DP[7]=DP[2]+1=3;
        9>1, 可能DP[7]=DP[1]+1=2;
        9>2, 可能DP[7]=DP[0]+1=2;
        最终DP[7]=5

| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | nums[index] | 2 | 1 | 5 | 3 | 6 | 4 | 8 | 9 | 7 | | DP[index] | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 |
|

i=8时

nums[8]=7, 7<9, 可能DP[8]=1;
        7<8, 可能DP[8]=1;
        7>4, 可能DP[8]=DP[5]+1=4;
        7>6, 可能DP[8]=DP[4]+1=4;
        7>3, 可能DP[8]=DP[3]+1=3;
        7>5, 可能DP[8]=DP[2]+1=3;
        7>1, 可能DP[8]=DP[1]+1=2;
        7>2, 可能DP[8]=DP[0]+1=2;
        最终DP[8]=5

| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | nums[index] | 2 | 1 | 5 | 3 | 6 | 4 | 8 | 9 | 7 | | DP[index] | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 | 4 |

最终，nums的最长递增子序列的长度为DP中的最大值5。nums中最长的递增子序列为以9结尾的：{2,5,6,8,9}或{2,3,4,8,9}或{2,3,6,8,9}或{1,5,6,8,9}或{1,3,6,8,9}或{1,3,4,8,9}。

可以从索引DP[7]=5的位置往前找DP依次递增的位置，构建序列。

最终代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() <= 1){
            return 1;
        }

        vector<int> dp(nums.size(), 1);
        // 当前最长递增子序列的长度和以nums[i]为结尾元素的最长递增子序列的长度
        int max_length=1; 
        for(int i=1; i<nums.size(); i++){
            for(int j=i-1; j>=0; j--){
                if(nums[i] > nums[j]){
                    dp[i] = max(dp[i], dp[j] + 1);
                }
                /*
                else{
                    dp[i] = max(dp[i], 1);   // 可省略，因为dp初始化为1，所以max()结果总是dp[i]
                }
                */
            }
            max_length = max(max_length, dp[i]);
        }
        return max_length;
    }
};

运行效率评价

Runtime: 280 ms, faster than 29.19% of C++ online submissions for Longest Increasing Subsequence.
Memory Usage: 10.5 MB, less than 35.89% of C++ online submissions for Longest Increasing Subsequence.