最长上升子序列

描述：

A numeric sequence of ai is ordered if a1 < a2 < ... < aN.

Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= 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.

输入格式：

There are several test cases. Every test case includes two lines.

The first line 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

When N is 0, it indicates test to end.

输出格式：

Output must contain a single integer for every test case ---- the length of the longest ordered subsequence of the given sequence.

分析：

这题还是需要用到动态规划的方法（存在子问题的重复问题），

对于第一个元素，最长的上升子序列肯定为1；

从第二个元素开始，每个向前比较，找到符合上升条件并且最大的一个，如果没有符合条件的，则当前元素最长上升子序列为1。

假设 f( i ）表示求对于第 i 个元素的最长上升子序列，存在递推关系：

f (i) = 1 i=1;

f (i) = f (j) + 1 a[i]>a[j] ( 1<j<i ) ;

f (i) = 1; 不存在 a[i]>a[j] ( 1<j<i );

代码如下：

#include<iostream>  
using namespace std;  
  
int a[1000];  
int b[1000];  
  
void func(int m){  
     b[1]=1;      //第一个肯定为1  
     int sum=0;  
     int max=0;  
     int besti=0;  
  
     for(int n=2;n<=m;n++){   //从第二个开始找  
         sum=0;  
         max=0;  
         besti=0;  
        for(int i=1;i<n;i++){  //向下比较每一个，找符合的最大  
            if(a[n]>a[i]) {  
               sum=b[i];  
               if(sum>max) { besti=i; max=sum; }  
            }  
        }  
         if(besti>0) b[n]=b[besti]+1;      //存在符合  
         else b[n]=1;  //否则为1  
     }  
}  
  
  
  
int main(){  
    int max=0;  
    int n;  
    do{  
    cin>>n;  
    if(n==0) break;  
    for(int i=1;i<=n;i++) cin>>a[i];  
    func(n);  
    max=0;  
    for(int i=1;i<=n;i++) {  
         if(b[i]>max) max=b[i];  
    }  
    cout<<max<<endl;  
    } while(n!=0);  
  
    return 0;  
  
}

补充：软件开发 , C++ ,