1. 题目

    给定一整数序列A1， A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大。例如： 整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为20。

    编程之美上的一道题，也是常考题目之一。

2. 解答

    属于基础动态规划。递推公式如下：

    假设序列为：a[0],a[1],...,a[n-1]， 定义两个新的序列：p[0],p[1],...,p[n-1]，和q[0],q[1],...,q[n-1]。

    p[k]表示从a[0]到a[k]的范围，包含a[k]的最大的子序列。显然p[k]=p[k-1]>0?(p[k-1]+a[k]):a[k]，p[0]=a[0]。即，如果从a[k]能向左发展，数值和会变大，就增长，否则就只有a[k]自己。

    q[k]表示从a[0]到a[k]的范围，最大的子序列长度。显然q[k]=max{q[k-1], p[k]}，即要么包含a[k]，要么不包含a[k]。

    而所求答案为q[n-1]。时间复杂度为2*n。

3. 备注

    答案很简单，不过快速反应出来，并且说得清楚不容易。