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]表示以nums[i]为最后一位的最长递增子序列的长度。

递推公式为dp[i] = max(dp[j] + 1) 其中 0 <= j < i 且 nums[j] < nums[i]。

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

下面介绍O(NlogN)的算法。

该算法的主要思想可以用一个例子来说明。如果有两个数nums[a]，nums[b]，且nums[a] < nums[b]，而dp[a] = dp[b]，即以这两个数截止的最长递增子序列的长度是相等的，那么如果后面还有数，很明显我们要优先选择nums[a]，因为它更小，选它则之后获得更长增长子序列的机会更大。

因此这里我们用len来记录目前已经发现的最长增长子序列的长度。

用一个int数组MinLastNumOfLenOf[k]来表示目前已经发现的，长度为k的最长增长子序列的最后一个元素的最小值。这里数组名字起这么长纯粹是为了好理解。

那么会发现MinLastNumOfLenOf中的值是递增的，即对于i < j有M[i] < M[j]。否则，假设M[j] < M[i] 且j > i，那么我们按照定义完全可以让M[i] 等于M[j]的值，这样会更优。同时，M[i]的值在算法运行过程中只降不增。

在实际进行中，len为当前我们已经发现的最长增长子序列的长度，而MinLastNumOfLenOf[len]则记录了该最长子序列的最后一个元素（最小的）。

当我们进行到nums[i]时，如果nums[i] > MinLastNumOfLenOf[len]，则明显我们获得了一个更长的增长子序列，因此将len加一，然后令MinLastNumOfLenOf[len] = nums[i]。

否则，如果nums[i] < MinLastNumOfLenOf[len]，则我们可以找到一个最小的下标k，k满足MinLastNumOfLenOf[k] > nums[i]，然后我们将MinLastNumOfLenOf[k]更新为nums[i]的值。这里，因为M数组的值是递增的，我们可以用二分查找来找到这个下标，复杂度为O(logn)。

可能你会有疑问，我们都已经发现了长度为len的子序列了，为什么还要更新前面MinLastNumOfLenOf[k]的值呢？因为实际上M[1]...M[len]串连起来就是我们的最长增长子序列。但是，如果我们将后续的一个数nums[i] < M[len]更新到M数组中，假设更新到了M[k]，则明显，M[1]...M[k]仍然是一个最长增长子序列，而M[1]...到M[k+1]以及后面的元素就不是了，因为我们新插入的这个数是后加进来的，也就是说在nums[i]中的下标i是要大于M[k+1]...M[len]这些数在nums中的下标的。每次我们更新M数组时总会有这个规律，而且，当我们将M[k]更新得更小后，则M[k+1]被更新的机会就更大，毕竟M[k]不可能无限小下去。而且，虽然M[k]更新后，M[1]...M[len]就无法构成一个合法的增长子序列，但我们已经用len保存了当前所发现的最长值，因此并无大碍。以上过程一直持续到我们找到一个新的数，而它仅小于M[len]时，M[len]被更新了，此时我们终于找到了一个长度为len且最后一个元素更小的子序列，而这使得后续找到更长的子序列的机会更大了！

 1 class Solution {
 2 public:
 3     int findInd(vector<int>& d, int num)
 4     {
 5         int left = 0, right = d.size() - 1;
 6         while (left < right)
 7         {
 8             int mid = (left + right) >> 1;
 9             if (d[mid] < num) left = mid + 1;
10             else if (mid != 0 && d[mid - 1] < num)
11                 return mid;
12             else right = mid;
13         }
14         return left;
15     }
16     int lengthOfLIS(vector<int>& nums) {
17         int n = nums.size();
18         if (n < 2) return n;
19         int len = 1;
20         vector<int> MinLastNumOfLenOf(2, 0);
21         MinLastNumOfLenOf[len] = nums[0];
22         for (int i = 1; i < n; i++)
23         {
24             if (nums[i] > MinLastNumOfLenOf[len])
25             {
26                 MinLastNumOfLenOf.push_back(nums[i]);
27                 len++;
28             }
29             else if (nums[i] < MinLastNumOfLenOf[len])
30                 MinLastNumOfLenOf[findInd(MinLastNumOfLenOf, nums[i])] = nums[i];
31         }
32         return len;
33     }
34 };