问题描述
采用动态规划策略设计并实现算法，求解最大子段和及最大子段和的起始下标和终止下标，要求算法的时间复杂性不超过O(n)。
最大子段和问题
给定由n个整数（可能为负整数）组成的序列a1, a2,…, an, 求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为
例如
当（a1，a2， a3， a4，a5，a6）= （-2，11，-4，13，-5，-2）时，最大子段和为 = 20，起始下标为2，终止下标为4。
下面这个程序时间复杂度极低为o（n）
#include<iostream>
using namespace std;
int MaxSum(int n, int a[], int &l, int &r)
{
int sum=0, b=0, i=0, bestI=0, bestJ=0;
for(int j = 1; j <= n; j++)
{
if(b > 0)
{
b += a[j];
}
else
{
b = a[j]; i = j;
}
if(b > sum)
{
sum = b; bestI = i; bestJ = j;
}
}
l = bestI;
r = bestJ;
return sum;
}
int main()
{
int flag[10] = {-2, 11, -4, 13, -5, 2};
//int flag[10] = {-7, 11, -4, -13, -5, -2};
int besti, bestj, sum;
sum = MaxSum(6, flag, besti, bestj);
cout<<"最大子段和: "<<sum<<endl;
cout<<"初始下标: "<<besti<<endl;
cout<<"最终下标: "<<bestj<<endl;
}
