Longest Increasing Subsequence

Posted on | In , |

题目

https://leetcode.com/problems/longest-increasing-subsequence/description/

-w948

想法

LIS

1
2
3
4
5
dp[N] = {1,}
for i 0..N:
    for j 0..i:
        if num[j] < num[i]:
            dp[i] = max(dp[i], dp[j] + 1)

很经典的DP，唉，DP就是这样，没想到的时候，怎么也觉得不顺，想到了，好优雅的设计
这是O( N^2 )的解法，还有O( NlogN )的解法，有时间再看

答案

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