300. Longest Increasing Subsequence

发表于 | 分类于 | |

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?

题意：最长上升子序列。

​ 最长上升子序列，应该是DP里面很经典的问题了，可是一开始想靠自己的想法把它推出来，结果还是有点难度。特别是在定义状态花费了太多时间，因为看到题目提示是O（N^2）的复杂度，所以以为状态会是dp[i][j]这种二维的形式。定势思维了，要改!

​ 后来再想，dp问题的核心在于划分子问题上。想清楚1：能否划分为子问题 ；2：怎么从子问题推导出母问题(状态转移) 才是王道啊！

​ 所以嘛，令dp[i]为以i为结尾的最长子序列。则dp[i]可以由前面怎么推出来呢？

​ 对于所有的0<=j\ nums[j]，那么可得dp[i] = dp[j] + 1;但是我们要求最长上升子序列，所以只需要维护所有j里面算出来dp[i]是最大的那个：dp[i] = max(dp[i], dp[j] + 1);**

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

​ 参考了下Discuss大神的O(nLogN)的做法，不是特别能理解，所以在先做个摘录。

tails is an array storing the smallest tail of all increasing subsequences with length i+1 in tails[i].
For example, say we have nums = [4,5,6,3], then all the available increasing subsequences are:

1
2
3
4
5
> len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
> len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
> len = 3   :      [4, 5, 6]            => tails[2] = 6
>
>

>

We can easily prove that tails is a increasing array. Therefore it is possible to do a binary search in tails array to find the one needs update.

Each time we only do one of the two:

1
2
3
4
> (1) if x is larger than all tails, append it, increase the size by 1
> (2) if tails[i-1] < x <= tails[i], update tails[i]
>
>

>

Doing so will maintain the tails invariant. The the final answer is just the size.

参考大神的想法自己写出O(nLogN)的c++代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//
// Created by chaopengz on 2017/12/2.
//

#include "head.h"

class Solution {
public:
    int lengthOfLIS(vector<int> &nums)
    {
        int len = nums.size();
        if (!len)
            return 0;
        vector<int> dp;
        vector<int>::iterator low;
        for (auto i:nums)
        {
            low = lower_bound(dp.begin(),dp.end(),i);

            if(low == dp.end())
                dp.push_back(i);
            else
                dp[low-dp.begin()] = i;
        }
        int ans = dp.size();
        return ans;
    }
};