最长递增子序列-动态规划

【问题描述】

　　有一个长度为N的乱序数组，请找到一个子序列，使得这个子序列元素的值依次递增，并且这个子序列的长度最长。注意，数组一旦给定，每个元素的位置就确定了，不可以交换元素位置。

　输入：第一行有一个数字N，表示数组的长度，1<=N<=1000，第二行有N个整数，用空格隔开 输出：由于最长递增子序列可能不唯一，所以只要输出长度即可。

【样例输入】

　　8

　　180 168 120 158 140 162 175 160

【样例输出】

　　 4

#include<iostream>
using namespace std;
int a[1001],dp[1001]; 

int main(){
    int n, maxL=0;
    cin>>n;
    // 180 168 120 158 140 162 175 160
    for(int i=1; i<=n; i++){
        cin>>a[i];
        dp[i]=1;
    }
    //fill(a+1, a+n+1, 1); // 数组a初始化为 1。 
    for(int i=2; i<=n; i++){ // 当前元素和其前方的所有元素进行比较。 
        for(int j=1; j<i; j++){
            if(a[i]>a[j]&&dp[j]+1>dp[i]){
                dp[i]=dp[j]+1;
            }
        }
    }
    for(int i=1; i<=n; i++){
        maxL=max(dp[i], maxL);
    }    
    cout<<maxL;
    return 0;
}