DP:有段时间没写题了，这道DP居然想了半小时
题目：最大上升子序列
思路：另开一个数组r保存：以当前值为结尾的最大上升子序列，则递推关系为:
r[i+1] = a[i+1] + max(r[0:i])
最后输出max(r[0:n])即可

#include <stdio.h>

int main()
{
//    freopen("C:/Users/yuanxing.shi/Documents/HDOJ/input.txt","r",stdin);
    int i,j,n,a[1024],r[1024],m;
    while(1)
    {
        scanf("%d",&n);
//        printf("%d ",n);
        if(0==n)
            break;
        for(i=0;i<n;i++)
        {
            scanf("%d",a+i);
        }
        for(i=0;i<n;i++)
        {
            if(0==i)
                r[i] = a[i];
            else
            {
                for(j=0,m=0;j<i;j++)
                {
                    if(a[j]<a[i] && r[j]>m)
                        m = r[j];
                }
                r[i] = a[i] + m;
            }
        }
        for(i=0,m=0;i<n;i++)
        {
            if(r[i]>m)
                m = r[i];
        }
        printf("%d\n",m);
    }
    return 0;
}

补充：数据存在溢出的可能用long long比用int好，不过只是数据集不作这方面的要求罢了.