算法最大字段及.doc

最大字段和
1题目分析与算法构造
当所有整数均为负值时定义其最大子段和为0。
由此可得，所求的最优值为：

算法构造：由bj的定义易知，
当bj-1>0时bj=bj-1+aj，否则bj=aj。
由此可得计算bj的动态规划递归式bj=max{bj-1+aj，aj}，1≤j≤n。
2．算法实现
#include<iostream>
using namespace std;
int MaxSum(int n,int a[])
{
int sum=0,b=0;
for(int i=1;i<=n;i++)
{
if(b>0)b+=a[i];
else b=a[i];
if(b>sum)sum=b;
}
return sum;
}

int main()
{
int n,a[100],m,maxsum;
cout<<"请输入整数序列的元素个数n: "<<endl;
cin>>n;
cout<<"请输入序列中各元素的值a[i](一共"<<n<<"个)" <<endl;
for(m=0;m<n;m++)
cin>>a[m];
int b[100];
for(m=0;m<n;m++)
b[m+1]=a[m];
maxsum=MaxSum(n,b);
cout<<"整数序列的最大子段和是："<<maxsum<<endl;
system("pause");
}

3运行结果：
请输入整数序列的元素个数n:
5
请输入序列中各元素的值a[i](一共5个)
5
-9
4
8
7
整数序列的最大子段和是：19
请按任意键继续. . .