LeetCode300. 最长递增子序列【动态规划】

喜欢ヅ旅行 2023-01-21 14:22 119阅读 0赞

难度：`中等`  
题目描述：

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

时间复杂度O(n2)

class Solution { 
    public:
        int lengthOfLIS(vector<int>& nums) { 
            int n = nums.size();
            int max_len = 1;
            int dp[n];
            for(int i=0;i<n;i++){ 
                dp[i]=1;
                for(int j=0; j<i; j++){ 
                    if(nums[j] < nums[i]){ 
                        dp[i] = max(dp[j]+1, dp[i]);
                        if(dp[i] > max_len){ 
                            max_len = dp[i];
                        }
                    }
                }
            }
            return max_len;
        }
    };

时间复杂度O(nlogn)

class Solution { 
    public:
        int lengthOfLIS(vector<int>& nums) { 
            int n = nums.size();
            int dp[n];
            dp[0] = nums[0];
            int dp_len = 1;
            for(int i=1;i<n;i++){ 
                if(nums[i]>=dp[dp_len-1]){ 
                    if(nums[i]>dp[dp_len-1])
                        dp[dp_len++]=nums[i];
                }else if(nums[i]<=dp[0]){ 
                    dp[0]=nums[i];
                }else{ 
                    int l=0,r=dp_len-1,mid=0;
                    while(l<=r){ 
                        mid=(l+r)/2;
                        if(dp[mid]==nums[i]){ 
                            break;
                        }
                        else if(dp[mid]>nums[i]){ 
                            if(l == r){ 
                                break;
                            }
                            r=mid;
                        }else{ 
                            l=mid+1;
                        }
                    }
                    dp[mid]=nums[i];
                }
            }
            return dp_len;
        }
    };