最大子序列和的总结 本文关键词：大子，序列
最大子序列和的总结 本文简介：最大子序列和第一种情况：可以一个不取【问题描述】：最大子序列和也叫数列的连续最大和，顾名思义，就是在一个长度为n的数列{An}中，求i，j（10thenf[i]:=f[I-1]+a[i]elsef[i]:=0;max:=-maxlongint;fori:=1tondoiff[i]>maxthenma
最大子序列和的总结 本文内容：
最大子序列和
第一种情况：可以一个不取
【问题描述】：最大子序列和也叫数列的连续最大和，顾名思义，就是在一个长度为n的数列{An}中，求i，j（10
then
f[i]:=f[I-1]+a[i]
else
f[i]:=0;
max:=-maxlongint;
for
i:=1
to
n
do
if
f[i]>max
then
max:=f[i];
程序代码二：迭代进行
best:=-maxlongint;
temp:=0;
for
i:=1
to
n
do
begin
temp:=temp+a[i]);
if
temp>best
then
best:=temp;
if
tempa[i]
then
f[i]:=f[I-1]+a[i]
else
f[i]:=a[i];
max:=-maxlongint;
for
i:=1
to
n
do
if
f[i]>max
then
max:=f[i];
第三种情况：至少要取两个。
1、解法一：动态规划求解，
2、样例求解过程：
1
2
3
4
5
6
A[i]
-3
4
9
-2
-5
8
F[i]
-3
只能取一个
-3+4=1
取两个
13=
max{4+9,9+1}
11=
Max{9-2,13-2}
6=
max{-2-5,11-5}
14=
Max{-5+8,6+8}
说明：以第4个元素为例：
选择一：取长度为2：9-2=7；
选择二：把元素a[4]连接到元素a[3]结尾的后面。F[3]+a[4]=13-2
两者最较大者。
3、动态规划方程为：
F[i]：表示以元素i结尾的至少要取两个的连续最大子序列的和
那么对于第i个元素来说，有两种选择：
选择一：因至少要选两个，所以和为a[i-1]+a[i];
选择二：把a[i]连接到a[i-1]元素结尾的长度至少为2的最大连续子序列后。此时和为f[i-1]+a[i];
两种情况选较大者。
所以动态方程：
f[i]:=max{a[i-1]+a[i],f[I-1]+a[i]}(i>=3)
(边界条件：f[1]=a[1];f[2]=a[1]+a[2])
5、
代码：
F[1]:=a[1];
f[2]:=a[1]+a[2];
for
I:=3
to
n
do
if
(f[I-1]+a[i])>a[i-1]+a[i]
then
f[i]:=f[I-1]+a[i]
else
f[i]:=a[i-1]+a[i];
max:=-maxlongint;
for
i:=2
to
n
do
if
f[i]>max
then
max:=f[i];
其它情况：
如2014年衢州市竞赛的转型，把相应的内容扩展到矩阵中而已。
5、求M子段和的最值。
问题描述：在一个长度为n的数列{An}中，求m个连续子序列，使得这m个连续子序列的和最大，且m个子序列无公共元素。特别地，若一子段的数全为负，则这个子段的和为0。（若两子段x[ij]与y[i’j’]不相交，则他们的关系是Ians[i,j]
then
ans[i,j]:=ans[i-1,k]+no[j];
end;
for
i:=1
to
n
do
if
ans[m,i]>best
then
best:=ans[m,i];
注意：红色部分为确定最大值的过程！因为ans[i,j]表示数列前j个元素中，i个无公共元素的子序列的最大和，且最大和不一定非要取完所有的元素，所以用一个循环来检测所有m的连续子序列的元素最大和，以确定全局最优值！
6、环形的最大连续子序列和。
方法同上，先断环并复制一份连接上就可以了。
7、矩阵中的最大连续子序列和
把矩阵压缩成线性序列就可以。