最长递增子序列

题目描述

给定一个序列X=(X1,X2,…,Xm)，求X的最长递增子序列。（子序列可以是不连续的，比如{5,6,7,1,2,8}的LIS是5,6,7,8）

说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(nlogn) 吗?

来源：LeetCode

解法一

因为是数组，求数组的最优解，问题太大了，我们能不能划分一下，分成多个子问题？这里子问题是需要跟问题对应的，即与递增子序列对应，我们把子问题划分为(X1…Xi)，LIS[i]是以Xi为结尾的最长递增子序列，最优子结构利用了递增的性质，即比较当前结尾元素和所有子问题结尾元素的大小，如果大，则在子问题解的基础上加1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        vector<int> dp(n, 1);
        int max_len = 1;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            max_len = max(max_len, dp[i]);
        }
        return max_len;
    }
};