DP-最长上升序列

thinking:两个循环,找小于自身的那个数,也就是到这个找到的数有几个最大上升序列了,在原基础上加1.然后接着往前找,挑出最大值赋值到这个数.

如 1 3 9 2 6 11

每隔数初值为1.则3的最大上升序列为2,9的最大上升序列有（3的最大上升序列）,（1的最大上升序列）,找最大加1,则为3,那么2的最大上升序列为(1）,则2的最大上升序列为2

.6的最大上升序列为(2的最大上升序列),(3的最大上升序列),(1的最大上升序列)找出最大,为(3),则6的最大上升序列为4,以此类推

题目:

 - Longest Ordered Subsequence Time Limit:2000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu Submit  Status

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_i1,  a_i2, ...,  a_iK), 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

4 代码:

#include <iostream> #define MAXN 99999 using namespace std; int a1[MAXN],b1[MAXN]; int main(){ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); int n; int i,j,k,l; cin >> n; for(i=0;i<n;i++){ cin >> a1[i]; b1[i]=1; } int maxn=1; for(i=0;i<n;i++){ for(j=0;j<i;j++) if(a1[j]<a1[i]&&b1[i]<=b1[j]) b1[i]=b1[j]+1; if(b1[i]>maxn)maxn=b1[i]; } cout << maxn << endl; return 0; }