300.最长上升子序列

题目描述

• 给你一个整数数组nums，找到其中最长严格递增子序列的长度。
  子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,7]的子序列.

示例1

输入： nums = [10,9,2,5,3,7,101,18]
输出： 4
解释 最长递增子序列是[2,3,7,101]，因此长度为4

示例2

输入： nums = [0,1,0,3,2,3]
输出 4

示例3

输入 nums = [7,7,7,7,7,7,7]
输出 1

提示

• 1<=nums.length<=2500
• -10^4<=nums[i]<=10^4

解题思路

1. 确定dp数组的含义
dp[i]表示i之前（包括i）以nums[i]结尾的最长递增子序列的长度
2. 确定递推公式
位置i上的最长递增子序列=位置j上0到i-1各个位置最长递增子序列+1的最大值 if(nums[i] > nums[j]) dp[i] = max(dp[j]+1, dp[i])
3. dp数组初始化
每个位置i对应的最长递增子序列初始值都是1
4. 确定遍历顺序

• dp[i]：根据0到i-1各个位置最长递增子序列推导而来，因此遍历顺序为从前往后
• dp[j]：只需遍历0到i-1，故其遍历顺序可任意

5. 打印dp数组

代码实现

• 核心模式

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

        // initialize the DP array
        vector<int> dp(nums.size(), 1);


        // traversal 
        for (int i = 1; i < nums.size(); i++){
            for (int j = 0; j <i; j++){
                if (nums[i] > nums[j]) dp[i] = std::max(dp[j] + 1, dp[i]);
            }

            if (dp[i] > numsLen) numsLen = dp[i];
        }       
        return numsLen;
    }
};

• ACM模式
dynamicPro.h

#include <iostream>
#include "dynamicPro.h"

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

        // initialize the DP array
        vector<int> dp(nums.size(), 1);

        int numsLen = 0;
        // traversal 
        for (int i = 1; i < nums.size(); i++){
            for (int j = 0; j <i; j++){
                if (nums[i] > nums[j]) dp[i] = std::max(dp[j] + 1, dp[i]);
            }

            if (dp[i] > numsLen) numsLen = dp[i];
        }

        printVector(dp);

        return numsLen;
    }
};

int main(){
    vector<int> case1 = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<int> case2 = {0, 1, 0, 3, 2, 3};
    vector<int> case3 = {7, 7, 7, 7, 7, 7, 7};

    Solution solution;
    cout << "Result1's DP array = " << solution.lengthOfLIS(case1) << endl;
    cout << "Result2's DP array = " << solution.lengthOfLIS(case2) << endl;
    cout << "Result3's DP array = " << solution.lengthOfLIS(case3) << endl;
    return 0;
}

• 输出

Result1's DP array = [1, 1, 1, 2, 2, 3, 4, 4]
4
Result2's DP array = [1, 2, 1, 3, 3, 4]
4
Result3's DP array = [1, 1, 1, 1, 1, 1, 1]
1