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?
方法1，利用动态规划的思路，设数组length[i]表示数组前面i个数中最大增长子数组的长度。初始化设置length[i]=1{i∈[0,n)} 算法时间复杂度：O(n2)
class Solution {public:int lengthOfLIS(vector<int>& nums) {if(nums.size()==0)return 0;vector<int> length(nums.size(),1);int ret=1;for(int i=0;i<nums.size();i++)for(int j=i+1;j<nums.size();j++)if(nums[i]<nums[j]){length[j]=max(length[j],length[i]+1);if(length[j]>ret)ret=length[j];}return ret;}};
#include<iostream>#include<vector>using namespace std;class Solution {private:int max(int a, int b) {return a > b ? a : b;}vector<int> nums;public:int lengthOfLIS(vector<int>& nums) {if (nums.size() == 0)return 0;vector<int> length(nums.size(), 1);vector<int> prev(nums.size(), -1);this->nums = nums;int pos, ret=0;for (int i = 0; i < nums.size(); i++) {for (int j = i + 1; j < nums.size(); j++) {if (nums[i] < nums[j]) {if ((length[i] + 1)>length[j]) {length[j] = length[i] + 1;prev[j]=i;}}}}for (int i = 0; i < nums.size(); i++) {if (length[i] > ret) {pos = i;ret = length[i];}}trace(prev,pos);cout << endl;return ret;}void trace(vector<int>&prev,int i) {if (prev[i] != -1)trace( prev,prev[i]);cout << nums[i] << " ";}};//注意：请注意形参赋值 以及 引用必须在构造函数中初始化int main() {int a[] = { 10, 9, 2, 5, 3, 7, 101, 18 };vector<int> b(a, a + 8);Solution * s = new Solution();cout << s->lengthOfLIS(b) << endl;return 0;}
开始1，5，8相继加入数组V，此时读到3，用3替换5，得到1，3，8；
再读6，用6替换8，得到1，3，6；
再读7，得到最终数组为1，3，6，7。最长递增子序列为长度
总结：当s[i]<v.back()只是提升了最长递增子序列继续增长的潜质，并没有改动数组的大小
class Solution {public:int lengthOfLIS(vector<int>& s) {// 不得不判断的特例if (s.size() == 0) return 0;// 先放入一個数字，免得稍后 v.back() 出错。vector<int> v;v.push_back(s[0]);for (int i = 1; i < s.size(); ++i){int n = s[i];//如果s[i]>v.back()，将其加入最长增长子序列if (n > v.back())v.push_back(n);else//否则用其更新数组v中第一个比他大的数，提升整个数组最长增长子序列继续增长的潜力*lower_bound(v.begin(), v.end(), n) = n;}return v.size();}};
300.Longest Increasing Subsequence
原文：http://www.cnblogs.com/zhoudayang/p/5008058.html