LeetCode300——Longest Increasing Subsequence

青旅半醒 2022-08-09 19:30 58阅读 0赞

题意：

最长上升子串，LIS问题，经典的动态规划问题。据说有用到二分的方法，这个还没有仔细研究，先说说朴素的方法：

动归方程可以如下描述：

dp\[i\] 表示以 nums\[i\]结尾的最长上升子串的长度。

为了得到dp\[i\]，我们首先要找出最大的dp\[j\] 其中 j 的范围是 \[0,i-1\]

当nums\[i\] > nums\[j\]时，dp\[i\]=上述最大值加1。

代码：

class Solution {
    public:
    	int lengthOfLIS(vector<int>& nums) {
    		if (nums.size() == 0 || nums.size() == 1)
    			return nums.size();
    		vector< int >dp(nums.size());//init
    		int result=0;
    		dp[0] = 1;
    		for (int i = 1; i < nums.size(); i++)
    		{
    			int maxNum = 0;
    			for (int j = 0; j < i; j++)
    			{
    				if (dp[j]>maxNum&&nums[j]<nums[i])
    				{
    					maxNum = dp[j];
    				}
    			}
    			dp[i] = maxNum+1;
    			result = dp[i] > result ? dp[i] : result;
    		}
    		return result;
    	}
    };

\----------------------------------**2015年11月15日更新**\---------------------------------

看了July的算法视频，发现了一种新的方法。。。

先对原序列进行排序生成新的有序序列 nums2

再对nums和nums2做LCS（最长公共子序列）运算。

之后测试后会补齐代码。

\----------------------------------**2017年2月5日更新**\---------------------------------

时隔一年多，学会了用LCS解决LIS的算法，不过在LeetCode上出现Memory Limit错误

方法很简单，就是先将原序列排序，去重，在对这两个序列做LCS算法。

class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            vector<int>copied_nums(nums.begin(),nums.end());
            sort(copied_nums.begin(),copied_nums.end());
            copied_nums.erase(unique(copied_nums.begin(),copied_nums.end()),copied_nums.end());
            int m=nums.size();
            int n=copied_nums.size();
            vector<vector<int>>dp(m+1,vector<int>(n+1));
            for(int i=0;i<m;++i)
            {
                for(int j=0;j<n;++j)
                {
                    if(nums[i]==copied_nums[j])
                    {
                        dp[i+1][j+1]=dp[i][j]+1;
                    }
                    else
                    {
                        dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                    }
                }
            }
            return dp[m][n];
        }
    };