[算法]-Longest Increasing Subsequence-白红宇

看微软笔试题遇到的。

Longest Increasing Subsequence(LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keeps increasing.For example, LIS of {2,1,4,2,3,7,4,6} is {1,2,3,4,6}, and its LIS length is 5.Considering an array with N elements , what is the lowest time and space complexity to get the length of LIS？

算法一：动态规划

#include 
    
     #include 
     
      using namespace std;#define SIZE 8 int s[SIZE]= {2,1,4,2,3,7,4,6};       // sequenceint length[SIZE];  // 第 x 格的值為 s[0...x] 的 LIS 長度void LIS(){    // 初始化。每一個數字本身就是長度為一的 LIS。    for (int i=0; i

算法二：

#include 
    
     #include 
     
      using namespace std;#define SIZE 8 int s[SIZE]= {2,1,4,2,3,7,4,6};       // sequenceint b[SIZE];// num为要查找的数,k是范围上限// 二分查找大于num的最小值，并返回其位置int bSearch(int num, int k)  {      int low=1, high=k;      while(low<=high)      {          int mid=(low+high)/2;          if(num>=b[mid])              low=mid+1;          else               high=mid-1;      }      return low;  }; void LIS(){    int low = 1, high = SIZE;    int k = 1;    b[1] = s[1];    for(int i=2; i<=SIZE; ++i)    {        if(s[i]>=b[k])            b[++k] = s[i];        else        {            int pos = bSearch(s[i], k);            b[pos] = s[i];        }    }    printf("%d", k); }int main(void)  {      LIS();    system("pause");      return 0;  }