leetcode 300. Longest Increasing Subsequence 最长递增子序列LISS + 十分经典的动态规划DP做法

谁借莪１个温暖的怀抱￠ 2022-06-08 14:37 171阅读 0赞

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,  
Given \[10, 9, 2, 5, 3, 7, 101, 18\],  
The longest increasing subsequence is \[2, 3, 7, 101\], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

这道题就是最经典的LISS最长递增子序列问题，直接DP。

要和这一道题一起学习[leetcode 368. Largest Divisible Subset 类似LISS最长递增子序列问题 + DP动态规划][leetcode 368. Largest Divisible Subset _LISS_ _ DP] 因为看起来不想管，其实就是一个问题。

建议和[leetcode 646. Maximum Length of Pair Chain 最长连续元素][leetcode 646. Maximum Length of Pair Chain] 和[leetcode 354. Russian Doll Envelopes 俄罗斯套娃 + 动态规划DP + 类似LISS最长递增子序列的做法][leetcode 354. Russian Doll Envelopes _ _ _DP _ _LISS]一起学习

代码如下：

/*
     * 最长递增序列LISS
     * 经典的DP做法
     * */
    class Solution 
    {
        public int lengthOfLIS(int[] nums) 
        {
            if(nums==null || nums.length<=0)
                return 0;
    
            int []pre=new int[nums.length];
            int []len=new int[nums.length];
            for(int i=0;i<nums.length;i++)
            {
                pre[i]=i;
                len[i]=1;
            }
    
            int maxLen=-1;
            for(int i=0;i<nums.length;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(nums[j]<nums[i] && len[j]+1>len[i])
                    {
                        len[i]=len[j]+1;
                        pre[i]=j;
                    }
                }
                maxLen=Math.max(maxLen, len[i]);
            }
            return maxLen;
        }
    }

下面是C++的做法，这是一道很经典的DP动态规划的解决

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int lengthOfLIS(vector<int>& nums)
        {
            if (nums.size() <= 0)
                return 0;
    
            vector<int> dp(nums.size(),1);
            int maxLen = -1;
            for (int i = 0; i < nums.size(); i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (nums[j]<nums[i] && dp[j] + 1>dp[i])
                        dp[i] = dp[j] + 1;
                }
                maxLen = max(maxLen,dp[i]);
            }
            return maxLen;
        }
    };

[leetcode 368. Largest Divisible Subset _LISS_ _ DP]: http://blog.csdn.net/jackzhang_123/article/details/78173447
[leetcode 646. Maximum Length of Pair Chain]: http://blog.csdn.net/jackzhang_123/article/details/78862409
[leetcode 354. Russian Doll Envelopes _ _ _DP _ _LISS]: http://blog.csdn.net/jackzhang_123/article/details/78173297