求最大连续子序列和

题目描述：

 　数组 int a[] = {-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4} ; 某几个连续的子序列其和最大，比如a0+a1 = -1 。a1+a2+a3+a4 = 78 。则[a1 a2 a3 a4]组成的数组即是所求。

分析：

　　如果能够找到每个位置结束的最大连续子串和，那么保留最大的和就能解决问题。当然，也可以找到每个位置开始的最大连续子串和，其实这种的话就是把数组反转（其实还是求得以结束位置的最大连续子串和的意思），还是求解原来的问题。

　　重点：能够想到设计一个以第j处结束的子序列的最大和数组b[j]。（这样就能保证连续性，妙...）

找出递推式：

  　 设b[j]表示第j处，以a[j] 结尾的子序列的最大和。
       则b[j] = max(a[j] + b[j-1] , a[j]) ，而我们的所求的答案，就是从1-n对b数组求最大值，并保留最大值。

示例代码：

#include <iostream>
using namespace std;

void  main()
{
    int a[10] = {-4 , 3 ,56 , -15 , 34 , 0 , -14 , 4};
    int b[10];
    b[0] = a[0];
    int max ;
    if(a[0] >0)
        max= a[0];
    else
        max = 0;
    for(int i=1;i<10;i++)
    {
        b[i] = (b[i-1] + a[i]) > a[i]  ? (b[i-1] + a[i]) : a[i];
        if(max < b[i]) max = b[i];
    }
    cout << max << endl;
    
    // 如果想保留子串的开始、结束位置，只需要在求b[i]用另外的变量保留位置就可以了.
}

输出：78