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(n²) 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(n²) 

length(j) =  max  { length(i) + 1 : if nums[i] < nums[n]  ,  length[j] }

           0≤i≤n-1

               i+1≤j≤n-1

然后取length[]数组中的最大值，返回即可

1. 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;
           
       }
   };

    

扩展问题：如何输出一个最大长度的增长子数组？

设置一个数组prev[],prev[i]记录当前第i个数应该接在那一个数字之后，然后利用回溯函数输出这个最长增长子数组。我们设置一个特殊的标记，如果prev[i]=-1，代表第i个数不接在任何数字之后，即最大增长子数组以这个数开头。初始化prev[i]=-1 0≤i≤n-1。在回溯函数中，如果prev[i]!=-1,就继续调用函数trace(prev,prev[i]),输出上一个最长增长子数组中的元素。

以下是程序示例以及输出的结果：

1. #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;
   }

    

输出：

方法2：时间复杂度  O(n log n)   *重难点

    首先建立数组v,将s[0]加入数组,对于i∈[1,n),如果s[i]>v.back(),就将s[i]加入数组v,行成一个更长的增长子序列，否则用s[i]更新数组中前面第一个比他大的数，提升数组长度继续提升的潜质。

举例：原序列为1，5，8，3，6，7

开始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()只是提升了最长递增子序列继续增长的潜质，并没有改动数组的大小

1. 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();
           
       }
   };