GroupBlog

Longest Ordered Subsequence

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 55383		Accepted: 24836

Description

A numeric sequence of a_i is ordered if a₁ < a₂ < ... < a_N. Let the subsequence of the given numeric sequence ( a₁, a₂, ..., a_N) be any sequence ( a_i₁, a_i₂, ..., a_{i_K}), where 1 <= i₁ < i₂ < ... < i_K<= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input

7
1 7 3 5 9 4 8

Sample Output

O(n2)

假设1...m中每个数字的最长递增子数列的个数都已知了。那么很容易就可以求出第m+1个数字对应的最长递增子序列的个数，方法就是遍历1....m里面的所有递增子序列个数，选出一个数字比m+1小的数字上的个数，然后这个个数+1就是m+1处的个数。这样就可以在O(n^2)的时间内求出最长递增子序列。

#include <iostream>  
#include <algorithm>  
#include <cstring>  
using namespace std;  
  
int a[1005];
int dp[1005];
int n;  
  
int LIS() {  
    int ans;
    int m;  
    dp[1] = 1;  
    ans = 1;  
    for(int i = 2;i <= n;i++) {  
        m = 0;  
        for(j = 1;j < i;j++)  
        {  
            if(dp[j] > m && a[j] < a[i])  
            m = dp[j];  
        }  
        dp[i] = m+1;  
        ans = max(dp[i],ans);
    }  
    return ans;  
}  
  
int main() {  
    while(cin >> n)  {  
        for(int i = 1;i <= n;i++) {
            cin >> a[i];
        }
        cout << LIS() << endl;
    }  
  
    return 0;  
}

O(n logn)

假设已经对1...m当中进行了最长递增子数列的分析，那么应该可以得出递增子序列长度为i(1<i<=m)的序列中最后一个数字最小的是多少。而这个数字应该可以构成一个递增序列T。

在对m+1进行分析的时候，可以直接在T当中进行二分查找，找到合适的位置而直接判断出m+1对应的最长递增子序列对应的值。而在判断结束之后，根据需要看是否要更新T中的数值。如果采取这种算法的话，算法的复杂度为O(nlogn)。

#include <iostream>  
#include <algorithm>  
#include <cstring>  
using namespace std;  
  
int a[1005];
int dp[1005];
int c[1005]; //存储递增子序列最大元素
int n;  
  
int bin(int size,int k) { //二分查找
    int t = 1;
    int r = size;  
    while(l <= r) {  
        int mid = (t + r) / 2;  
        if(k > c[mid] && k <= c[mid+1]) {  
            return mid + 1;  
        } else if(k < c[mid]) {
            t = mid - 1;  
        } else {  
            l = mid + 1;  
        }
    }  
}  
  
int LIS() {  
    int ans = 1;  
    c[1] = a[1];  
    dp[1] = 1;  
    for(i = 2; i <= n; i++) {  
        if(a[i] <= c[1]) {  
            j = 1;  
        } else if(a[i] > c[ans]) {  
            j = ++ans;  
        } else {  
            j = bin(ans,a[i]);
        }
        c[j] = a[i];  
        dp[i] = j;  
    }  
    return ans;  
}  
  
int main()  {  
    while(cin >> n) {  
        for(i = 1; i <= n; i++)  
            cin >> a[i];
        cout << LIS() << endl;
    }  
  
    return 0;  
}