[算法]-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 <iostream>
#include <vector>
using namespace std;
#define SIZE 8 
int s[SIZE]= {2,1,4,2,3,7,4,6};       // sequence
int length[SIZE];  // 第 x 格的值為 s[0...x] 的 LIS 長度

void LIS()
{
    // 初始化。每一個數字本身就是長度為一的 LIS。
    for (int i=0; i<SIZE; i++) length[i] = 1;

    for (int i=0; i<SIZE; i++)
        // 找出 s[i] 後面能接上哪些數字，
        // 若是可以接，長度就增加。
        for (int j=i+1; j<SIZE; j++)
            if (s[i] < s[j])
                length[j] = max(length[j], length[i] + 1);

    // length[] 之中最大的值即為 LIS 的長度。
    int n = 0;
    for (int i=0; i<SIZE; i++)
        n = max(n, length[i]);
    cout << "LIS的長度是" << n;
}

int main(void)  
{  
    LIS();
    system("pause");  
    return 0;  
}

#include <iostream>
#include <vector>
using namespace std;
#define SIZE 8 
int s[SIZE]= {2,1,4,2,3,7,4,6};       // sequence
int 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;  
}