问题描述
给定由n个整数（可能为负整数）组成的序列
a
1
,
a
2
,
…
,
a
n
a_1,a_2,…,a_n
a
1
,
a
2
,
…
,
a
n
，求该序列形如
∑
k
=
i
j
a
k
\sum_{k=i}^j a_k
∑
k
=
i
j
a
k
的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依此定义，所求的最优值为
m
a
x
{
0
,
m
a
x
∑
k
=
i
j
a
k
(
1
≤
i
≤
j
≤
n
)
}
max\{ 0,max \sum_{k=i}^j a_k \left(1\le i \le j \le n\right)\}
m
a
x
{
0
,
m
a
x
k
=
i
∑
j
a
k
(
1
≤
i
≤
j
≤
n
)
}
例如当
(
a
1
,
a
2
,
a
3
,
a
4
,
a
5
,
a
6
)
=
(
−
2
,
11
,
−
4
,
13
,
−
5
,
−
2
)
\left(a_1,a_2,a_3,a_4,a_5,a_6\right)=\left(-2,11,-4,13,-5,-2\right)
(
a
1
,
a
2
,
a
3
,
a
4
,
a
5
,
a
6
)
=
(
−
2
,
1
1
,
−
4
,
1
3
,
−
5
,
−
2
)
时，最大子段和为
∑
k
=
2
4
a
k
=
20
\sum_{k=2}^4 a_k=20
∑
k
=
2
4
a
k
=
2
0
简单算法
最大子段和问题简单算法改进后的代码 。对所有的 ( i, j )对，顺序求和ai + … + aj，并比较出最大的和，标识该子段的首末位置。时间复杂度为
O
(
n
2
)
O(n^2)
O
(
n
2
)
#include <iostream>
using namespace std;
int MaxSum(int n,int *a,int &besti,int &bestj)
{
int sum = 0;
for(int i = 0;i < n;i++)
{
int thissum = 0;
for(int j = i;j < n;j++)
{
thissum += a[j];
if(thissum > sum)
{
sum = thissum;
besti = i;
bestj = j;
}
}
}
return sum;
}
int main()
{
int n = 6;
int a[] = {-2,11,-4,13,-5,-2};
int besti;
int bestj;
cout<<"最大子段和为："<<MaxSum(n,a,besti,bestj)<<endl;
cout<<"起始位置："<<besti<<endl<<"终止位置："<<bestj;
return 0;
}
递归算法
针对最大子段和这个具体问题本身的结构，还可以从算法设计的策略上对上述
O
(
n
2
)
O(n^2)
O
(
n
2
)
计算时间算法加以更深刻的改进。从这个问题的解的结构可以看出，它适合用
分治法
求解。
如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两个段的最大子段和，则a[1:n]的最大子段和有三种情形：
- a[1:n]的最大子段和与a[1:n/2]的最大子段和相同；
- a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同；
-
a[1:n]的最大子段和为
∑k
=
i
j
a
k
\sum_{k=i}^j a_k
∑
k
=
i
j
a
k
，且
1≤
i
≤
n
/
2
,
n
/
2
+
1
≤
j
≤
n
1\le i\le n/2,n/2+1\le j\le n
1
≤
i
≤
n
/
2
,
n
/
2
+
1
≤
j
≤
n
第1和第2种情形可递归求得。对于第三种情况，容易看出，a[n/2]与a[n/2+1]在最优子序列中。因此，可以在a[1:n/2]中计算出
s
1
=
m
a
x
∑
k
=
i
n
/
2
a
[
k
]
(
1
≤
i
≤
n
/
2
)
s_1=max \sum_{k=i}^{n/2} a[k] (1\le i\le n/2)
s
1
=
m
a
x
∑
k
=
i
n
/
2
a
[
k
]
(
1
≤
i
≤
n
/
2
)
，并在a[n/2+1:n]中计算出
s
2
=
m
a
x
∑
k
=
n
/
2
+
1
i
a
[
k
]
(
n
/
2
+
1
≤
i
≤
n
)
s_2=max \sum_{k=n/2+1}^i a[k] (n/2+1\le i\le n)
s
2
=
m
a
x
∑
k
=
n
/
2
+
1
i
a
[
k
]
(
n
/
2
+
1
≤
i
≤
n
)
，则
s
1
+
s
2
s_1+s_2
s
1
+
s
2
即为出现情形3时的最优质。据此可设计出求最大子段和的分治算法如下，该算法的时间复杂度是
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
：
#include<iostream>
using namespace std;
int MaxSubSum(int *a,int left,int right)
{
int sum = 0;
if(left == right)
sum = a[left]>0?a[left]:0;
else
{
int center = (left + right)/2;
int leftsum = MaxSubSum(a,left,center);
int rightsum = MaxSubSum(a,center+1,right);
int s1 = 0;
int lefts = 0;
for(int i = center;i >= left;i--)
{
lefts += a[i];
if(lefts > s1)
s1 = lefts;
}
int s2 = 0;
int rights = 0;
for(int i = center+1;i <= right;i++)
{
rights += a[i];
if(rights > s2)
s2 = rights;
}
sum = s1 + s2;
if(sum < leftsum)
sum = leftsum;
if(sum <rightsum)
sum = rightsum;
}
return sum;
}
int MaxSum(int n,int *a)
{
return MaxSubSum(a,0,n-1);
}
int main()
{
int n = 6;
int a[] = {-2,11,-4,13,-5,-2};
cout<<"最大子段和为："<<MaxSum(n,a)<<endl;
return 0;
}
动态规划算法
对上述分治算法的分析中注意到，若记
b
[
i
]
=
m
a
x
{
∑
k
=
i
j
a
[
k
]
}
(
1
≤
i
≤
j
,
1
≤
j
≤
n
)
b[i]=max\{\sum_{k=i}^j a[k]\} \left(1\le i\le j,1\le j\le n\right)
b
[
i
]
=
m
a
x
{
k
=
i
∑
j
a
[
k
]
}
(
1
≤
i
≤
j
,
1
≤
j
≤
n
)
，则所求的最大子段和为
m
a
x
1
≤
i
≤
j
≤
n
∑
k
=
i
j
a
[
k
]
=
m
a
x
1
≤
j
≤
n
m
a
x
1
≤
i
≤
j
∑
k
=
i
j
a
[
k
]
=
m
a
x
1
≤
j
≤
n
b
[
j
]
max_{1\le i\le j\le n} \sum_{k=i}^j a[k]=max_{1\le j\le n} max_{1\le i\le j} \sum_{k=i}^j a[k]=max_{1\le j\le n} b[j]
m
a
x
1
≤
i
≤
j
≤
n
k
=
i
∑
j
a
[
k
]
=
m
a
x
1
≤
j
≤
n
m
a
x
1
≤
i
≤
j
k
=
i
∑
j
a
[
k
]
=
m
a
x
1
≤
j
≤
n
b
[
j
]
由b[j]的定义易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。由此可得计算b[j]的动态规划递归式为
b
[
j
]
=
m
a
x
{
b
[
j
−
1
]
+
a
[
j
]
,
a
[
j
]
}
,
1
≤
j
≤
n
b[j]=max\{b[j-1]+a[j],a[j]\},1\le j\le n
b
[
j
]
=
m
a
x
{
b
[
j
−
1
]
+
a
[
j
]
,
a
[
j
]
}
,
1
≤
j
≤
n
因此，可设计出求最大子段和的动态规划算法如下：
#include<iostream>
using namespace std;
int MaxSum(int n,int *a,int &besti,int &bestj)
{
//b表示的是以元素a[i]为结尾的最大子段和
int sum = -1, b = 0,flag;
for(int i = 0;i < n;i++)
{
if(b > 0) b += a[i];
else
{
b = a[i];
flag=i;
}
if(b > sum)
{
sum = b;
besti=flag;
bestj=i;
}
}
return sum;
}
int main()
{
int n = 6;
int a[] = {-2,11,-4,13,-5,-2};
int besti=0,bestj=n-1;
int sum=MaxSum(n,a,besti,bestj);
if(sum==-1) sum=0;
cout<<"最大子段和为："<<sum<<endl;
cout<<"初始位置："<<besti<<"末尾位置："<<bestj<<endl;
return 0;
}
上述算法显然需要时间和空间复杂度均为
O
(
n
)
O(n)
O
(
n
)