数据结构之---求最大字段和, 时间复杂度o(n)算法

问题描述采用动态规划策略设计并实现算法,求解最大子段和及最大子段和的起始下标和终止下标,要求算法的时间复杂性不超过O(n)。最大子段和问题给定由n个整数(可能为负整数)组成的序列a1, a2,…, an, 求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义,所求的最优值为 例如当(a1,a2, a3, a4,a5,a6)= (-2,11,-4,13,-5,-2)时,

问题描述

采用动态规划策略设计并实现算法,求解最大子段和及最大子段和的起始下标和终止下标,要求算法的时间复杂性不超过O(n)。

最大子段和问题

给定由n个整数(可能为负整数)组成的序列a1, a2,…, an, 求该序列形如 的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义,所求的最优值为

例如

当(a1,a2, a3, a4,a5,a6)= (-2,11,-4,13,-5,-2)时,最大子段和为 = 20,起始下标为2,终止下标为4。

下面这个程序时间复杂度极低为o(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}
越来越多的平台(微信公众平台,新浪微博,简书,百度打赏等)支持打赏功能,付费阅读时代越来越近,特此增加了打赏功能,支持微信打赏和支付宝打赏。坚持原创技术分享,您的支持将鼓励我继续创作!