用动态规划解决

不错，不过动态规划不是最好的。

这里还有一种方法！
一个nlogn的最大上升子序列长度算法[转]

作者： Jedidiah

传统的最大上升子序列采用n2的动态规划算法，就求解一个最大上升子序列的具体序列来说，暂时找不到更快的算法，但是如果只需要求解这个序列的长度，则存在一个更快的算法，复杂度是nlog2n。


　　对于一个序列a[0]...a[n]，设F[i]表示到第i个数为止的最大上升子序列，我们考虑如这种情况，存在0<=y<x<i=n，若满足

(1) y<x<i;

(2) a[x]<a[y]<a[i];  

(3) |F[x]| == |F[y]|;

(4) a[j] < a[x], y < j < x

　　则此时F[i]应该由F[x]扩展而来，因为可能存在z满足

(1) y<x<z<i;  

(2) a[x]<a[z]<a[y]<a[i]

(3) z < min{j | a[j]>a[y], j > x}

　　则此时用F[x]扩展得到F[i]将长于F[y]扩展得到的子序列。 由此可得出结论，原序列第i个元素之前最长子序列的解可能存在很多，但我们只需要尽可能使得那个最长子序列的最后一个元素的值最小，就能向后扩展得到原串最长子序列。

　　求解的过程依然是一个动态规划的过程，我们采用一个数组d[k]，来描述到状态i时长度为k的子序列最后一个元素的最小值。从状态i-1转移到状态i时，a[i]的加入影响到数组中的d[k]，k满足

k = max{a[i]>d[j]} + 1

此时有

d[k] = min{d[k], a[i]}

　　由此我们会发现数组d一个明显的特征，即d是一个单调上升的序列，利用这个特性，我们可以采用二分法来查找k的值，这样使得整体的时间复杂度从原来的n2变为nlog2n，但是在设计过程中应该要注意到数组d的首元素和尾元素的处理。最后，我们所需要的值就是在末状态时d数组的最大下标值，这里值得注意的是数组d的下表的最大值应该是在变化的——反观定义则可明显地得到这个特性。

　　一下是一段源代码，测试过一个小数据，设计中发现整个算法的难点在于二分法查找的设计。

#include <cstdio>
#include <cstdlib>
#include <climits>
using namespace std;

int max_subsequence ( const int a[ ], const int size )
{
    int d[ size ], n;
    d[ n = 0 ] = a[ 0 ];
    for ( int i = 1; i < size; i++ )
        if ( d[ n ] < a[ i ] )
            d[ ++n ] = a[ i ];
        else if ( d[ 0 ] > a[ i ] )
            d[ 0 ] = a[ i ];
        else
        {
            int left = 0, right = n, mid = n / 2, key = a[ i ];
            while ( left < right )
                if ( d[ mid ] == key )
                {
                    mid--;
                    break;
                }
                if ( d[ mid ] > key )
                {
                    right = mid;
                    mid = ( left + right ) / 2;
                }
                else if ( mid > left )
                {
                    left = mid;
                    mid = ( left + right ) / 2;
                }
                else
                    break;
            if ( d[ mid + 1 ] > key )
                d[ mid + 1 ] = key;
        }
    return n + 1;
}

int main ( )
{
    int n;
    scanf ( "%d", &n );
    int a[ n ];
    for ( int i = 0; i < n; i++ )
        scanf ( "%d", &a[ i ] );
    printf ( "%d\n", max_subsequence ( a, n ) );
    system ( "pause" );
}

还有 O(N) 的算法，而且代码巨短。

int MaxSubsequenceSum(const int A[],int N)
{
    int ThisSum, MaxSum, j;
    ThisSum = MaxSum =0;
    for(j=0; j < N; j++)
    {
        ThisSum += A[j];
        if(ThisSum > MaxSum)
            MaxSum = ThisSum;
        else if(ThisSum < 0)
            ThisSum = 0;
    }
    return ThisSum;
}