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. 求数组中最长递增子序列
这题是编程之美的，看了半天才看明白。。。 考察第i+1个元素的时候考虑前面i个元素的情况
对于前面i个元素的任何一个递增子序列，如果这个子序列的最大的元素比nums[i+1]小，那么就可以将nums[i+1]加在这个子序列后面，构成一个新的递增子序列。
因此，我们希望找到前i个元素中的一个递增子序列，使得这个递增子序列的最大的元素比nums[i+1]小，长度尽量地长。这样将nums[i+1]加在该递增子序列后，便可找到以nums[i+1]为最大元素的最长递增子序列。
假设LIS[i]为以nums[i]为最大元素的最长递增子序列的长度 MaxV[j]为长度为j的递增子序列最大元素的最小值 那么长度为LIS[i]的递增子序列最大元素的最小值为MaxV[LIS[i]] 维护了这些值，那么，在算法中就可以利用相关的信息来减少判断的次数
Accepted Code
class Solution {public: int find(vector<int> array,int begin,int end,int key) { if(begin==end) return begin; int mid=0; while(begin<=end) { mid=(begin+end)>>1; if(array[mid]>=key) end=mid-1; else { if(mid==end) return end; else if(array[mid+1]>key) return mid; else begin=mid+1; } } return 0; } int lengthOfLIS(vector<int>& nums) { int N=nums.size(); if(N<2) return N; //以nums[i]为最大元素的最长递增子序列的长度LIS[i] vector<int> LIS(N,1); //长度为i的递增子序列最大元素的最小值MAXV[i] vector<int> MAXV(N+1,0); MAXV[0]=INT_MIN; MAXV[1]=nums[0]; int maxLength=1; //数组最长递增子序列的长度 for(int i=1;i<N;i++) { int j; //find为二分查找函数，替换下面注释的代码 j=find(MAXV,0,maxLength,nums[i]); LIS[i]=j+1; /* for(j=maxLength;j>=0;j--) { if(nums[i]>MAXV[j]) { LIS[i]=j+1; break; } } */ //更新长度为LIS[i]的递增子序列最大元素的最小值和maxLength if(maxLength<LIS[i]) { maxLength=LIS[i]; MAXV[LIS[i]]=nums[i]; } //更新长度为LIS[i]的递增子序列最大元素的最小值 else if(nums[i]<MAXV[j+1]) { MAXV[j+1]=nums[i]; } } return maxLength; }};新闻热点
疑难解答
