动态规划_最大上升子序列

一个序列有N个数：A[1],A[2],…,A[N]，求出最长上升子序列的长度（LIS：longest increasing subsequence)。例如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 5, 9) , (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 9) ，(1, 3, 5, 8)和(1, 3, 4, 8).

#include <iostream>

using namespace std;

int daynamic(int* a,int length){
    int *maxCount = new int[length];//maxCount[i]表示以a[i]结尾的的最大上升子序列长度
    for(int i=0; i<length; i++){
        maxCount[i] = 1;
    }
    int max = 1;
    for(int i=1; i<length; i++){
        for(int j=0; j<i ;j++){
            if(a[j]<a[i] && maxCount[j]+1>maxCount[i]){
                maxCount[i] = maxCount[j]+1;
            }
            if(maxCount[i]>max)
                max = maxCount[i];
        }
    }
    delete []maxCount;
    return max;
}

int main()
{
    int a[8] = {3,4,5,9,7,1,2,8};
    int max = daynamic(&a[0], 8);
    cout << max << endl;
    return 0;
}