最大子段和
最大子串和 实验题目
给定n个整数组成序列,求该序列的子段和的最大值,当所有整数均为负数时,其最
大子段和为0.
实验目的
(1)深刻掌握动态规划法的设计思想并能熟练运用;
(2)理解这样一个观点:同样的问题可以用不同的方法解决,一个好的算法是反复修
正的结果。
实验要求
()分别用蛮力法,分治法和动态规划法设计最大子段和问题的算法
()比较不同的算法的时间性能;
()给出测试数据,写出程序文档。 源代码
//蛮力法
#include using namespace std; void main()
{
int n,j,i,sum,max=0;
int a[100],b[100];
cout<<"输入序列元素个数:";
cin>>n;
cout<<"输入序列元素:"<>a[i];
for(j=1;j<=n;j++)
{
b[j]=0;
sum=0;
for(i=j;i<=n;i++)
{
sum=sum+a[i];
if(sum>b[j])
{
b[j]=sum;
}
continue;
}
}
for(j=1;j<=n;j++)
{
if(b[j]>max)
max=b[j];
}
cout<<"最大子串和为:"<
using namespace std; int maxsum(int a[],int left,int right)
{
int sum=0;
int i,j,s1,s2,lefts,rights,center,leftsum,rightsum;
if(left==right)
{
if(a[left]>0)
sum=a[left];
else
sum=0;
}
else
{
center=(left+right)/2;
leftsum=maxsum(a,left,center);
rightsum=maxsum(a,center+1,right);
s1=0;lefts=0;
for(i=center;i>=left;i--)
{
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}
s2=0;rights=0;
for(j=center+1;j<=right;j++)
{
rights+=a[j];
if(rights>s2)
s2=rights;
}
sum=s1+s2;
if(sum>n;
cout<<"输入序列元素:"<>a[i];
l=n%2;
r=n-l;
cout<<"最大子段和为:"< using namespace std; void maxsum();
void main()
{
maxsum();
}
void maxsum()
{
int i,j,n,k=1;
int max=0,sum=0;
int a[100],b[100];
cout<<"输入序列元素个数:";
cin>>n;
cout<<"输入元素:"<>a[i];
}
b[1]=a[1];
for(i=2;i<=n;i++)
{
if(b[i-1]<=0)
b[i]=a[i];
else
b[i]=b[i-1]+a[i];
}
for(j=1;j<=n;j++)
{
if(max
本文档为【最大子段和】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。