LeetCode 300. Longest Increasing Subsequence

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

Example:

Input: [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. 

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n²) complexity.

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

解析：对于给出的数组，获取最长递增子序列，考虑动态规划的方法。因为这里只需要求序列的长度，所以假设dp[i]表示以i字符结尾的最长递增子序列长度。采用两层循环，外层循环i从0到nums.size()，处理每个字符，内层循环从0到当前位置i。然后挨个判断nums[j]是否小于nums[i]，如果小于则在nums[j]基础上增加nums[i]形成一个递增子序列，此时dp[i]=dp[j]+1，另外选择最大长度dp[i]=max(dp[i],dp[j]+1)，同时设置一个数值，保存每一步计算中的最大值。代码如下：

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

参考：https://www.cnblogs.com/grandyang/p/4938187.html