题目描述

Example: Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], the length is 4. Note: There may be more than one result, 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?

思路

这是一个经典的动态规划算法，假设v[i]代表最后节点为第i个节点的最长递增子序列的长度，那么更新的状态方程为：

$v[i]=max(v[j])+1,其中j到i是连通的。$

O(n²)级别的算法一

class Solution { public: int lengthOfLIS(vector<int>& nums) { int * length = new int[nums.size()](); int max = 0, result = 0; for (int i = 0; i < nums.size(); i++) { max = 0; for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { max = max < length[j] ? length[j] : max; } } max++; length[i] = max; result = result < max ? max : result; } delete [] length; return result; } };

仍需努力仍需努力。

O(nlog(n))级别的算法二

之前我们在更新时，不得不遍历整个位于当前元素之前的元素来更新长度，有没有更好的方法呢？

在此之前，我们需要先确认递增序列的几个性质：

如果有一个长度为m的递增子序列A，当新的元素K加入时，要形成一条长为m+1的新序列，则K必须大于A的最后一个元素——记为last(A)。 如果有两个长度均为m的递增子序列A和B，那么当K大于min(last(A), last(B))时，会获得一条长为m+1的新序列。 令B[i] = k的含义为：长度为i的最短子序列的最小的最后一个值为k，那么当i变大时，B[i]是严格递增的。（这个在直观上很好想象，当然通过反证法也是可以证明的）。 如果有c > a 且 c < b， 且B[m] = a, B[m+1] = b, 那么B[m+1]=c。

所以，由上文的性质一和二，推出了性质三的数据结构的性质。而最后一个性质给出了这种结构的更新方法，以及严格递增下二分法的实现可能。 代码如下：

class Solution { public: int bisearch(int start, int end, int* S, int key) { if (S[end] < key) { return end+1; } //针对（2,2）这种情况 if (S[end] == key) { return end; } int mid = (start+end)/2; if (S[mid] > key) { if ( S[mid-1] < key) { return mid; } return bisearch(start, mid-1, S, key); } return bisearch(mid+1, end, S, key); } int lengthOfLIS(vector<int>& nums) { //针对[] if (nums.empty()) { return 0; } int * length = new int[nums.size()+1](); int pos = 0, end = 1; length[1] = nums[0]; //针对负数情况 length[0] = -10086; for (int i = 1; i < nums.size(); i++) { pos = bisearch(1, end, length, nums[i]); end = end < pos ? pos:end; length[pos] = nums[i]; } delete [] length; return end; } };

撒花儿~