300-Longest Increasing Subsequnce-最长递增子序列

问题描述

链接： https://leetcode.com/problems/longest-increasing-subsequence/description/

Given an integer array nums, return the length of the longest strictly increasing subsequence

解释：给定一个数组nums，返回长的严格递增子序列。

案例：

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.

基本思想

经典题型。
构造数组dp,大小等于nums的大小。

• \(dp[i]\): 以 \(nums[i]\)为结尾的最长严格递增子序列
• 则 \(dp[i]\) 依赖于 \(nums[0~ i-1]\) 比 \(nums[i]\)小的数，对应的下标index相应的\(dp[index]\)
• 其更新公式如下：
  • \(dp[i]\) = \(max(dp[j]+1)\) \(\quad\) 其中\(0<j<(i-1) \quad and \quad nums[j]<nums[i]\)$

时间复杂度 \(o(n^2)\)

代码

C++

    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n<=1) return n;
        vector<int> dp(n,1); // dp[i]表示以nums[i]为结尾的最长递增子序列
        int res = 0;
        for(int i=1;i<n;++i) {
            int t = 1;
            for(int j=0;j<i;++j) {
                if (nums[j]<nums[i]) {
                    t = max(t, dp[j]+1);
                }
            }
            dp[i] = t;
            res = max(res, dp[i]);
        }
        return res;
    }

python

    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n<=1: return n
        dp=[1] * n
        res = 1
        for i in range(1,n):
            t = 1
            for j in range(0,i):
                if nums[i] > nums[j]:
                    t = max(t, dp[j]+1) 
            dp[i] = t
            res = max(res, dp[i])
        return res