总时间限制: 2000ms 内存限制: 65536kB

描述

A numeric sequence of a is ordered if a < a < … < a. Let the subsequence of the given numeric sequence (a, a, …, a) be any sequence (a, a, …, a), where 1 ≤ i < i < … < i ≤ 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.

输入

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 file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

样例输入

7
1 7 3 5 9 4 8

样例输出

思路

找子问题

求序列的前n个元素的最长上升子序列是个子问题, 但这样分解不具备无后效性.

求以 a (k=1,2, 3…N)为终点的最长上升子序列是一个不错的子问题.
一个上升子序列最右边的那个数, 称为改子序列的终点.

虽然这个子问题和原问题形式上并不完全一样, 但是只要这N个子问题都解决了, 那么这N个子问题的解中, 最大的那个就是整个问题的解.

确定状态

子问题只和一个变量—数字的位置有关. 因此序列中数的位置k就是状态, 而状态k对应的值, 就是以 a 为终点的最长上升上升子序列的长度.
状态一共有N个.

找出状态转移方程

设maxLen(k)表示以 a为终点的最长上升子序列的长度, 那么:

$POJ 2533 Longest Ordered Subsequence - 图1$ %20%3D%20%0A%5Cbegin%7Bcases%7D%0A1%2C%20%26k%20%3D%201%5C%5C%0Amax%5C%7B%20maxLen(i)%20%5C%7D%20%2B%201%2C%20%26i%20%5Cin%20%5B1%2C%20k)%5C%20%E4%B8%94%5C%20a_i%20%3C%20a_k%5C%20%E4%B8%94%5C%20k%20%5Cneq%201%20%5C%5C%0A%5Cend%7Bcases%7D%0A#card=math&code=maxLen%28k%29%20%3D%20%0A%5Cbegin%7Bcases%7D%0A1%2C%20%26k%20%3D%201%5C%5C%0Amax%5C%7B%20maxLen%28i%29%20%5C%7D%20%2B%201%2C%20%26i%20%5Cin%20%5B1%2C%20k%29%5C%20%E4%B8%94%5C%20a_i%20%3C%20a_k%5C%20%E4%B8%94%5C%20k%20%5Cneq%201%20%5C%5C%0A%5Cend%7Bcases%7D%0A)

maxLen(k)的值, 就是在 a 左边, 终点数值小于 a, 且长度最大的那个上升子序列的长度再加1.

因为 a左边任何终点小于 a 的子序列, 加上 a 后就能形成一个更长的上升子序列.

“人人为我”递推型动归程序

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
int a[MAXN];
int maxLen[MAXN];
int main() {
    int N;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++) {
        scanf("%d", &a[i]);
        maxLen[i] = 1;
    }
    for(int i = 2; i <= N; i++) {
        /* 每次求以第i个为终点的最长上升子序列的长度 */
        for(int j = 1; j < i; j++) {
            /* 查看以第j个数为终点的最长上升子序列 */
            if( a[i] > a[j] )
                maxLen[i] = max(maxLen[i], maxLen[j] + 1);
        }
    }
    cout << *max_element(maxLen+1, maxLen + N + 1);
    return 0;
}