首页 > 编程语言 > 详细

《求一个数组的连续的最大子数组之和》

时间:2015-03-22 21:00:00      阅读:346      评论:0      收藏:0      [点我收藏+]

                                                               《求一个数组的连续的最大子数组之和》 

设计思想:一般的,求一个数组的最大子数组之和即是按数组顺序依次让前几个数的和与下一个数进行比较,设一变量来装每次比较后的较大的数,依此进行到数组终端;但是考虑到求的是连续的子数组,则应该想到除了在按顺序上的连续外,还得考虑到末端与首端的连续,所以按数组顺序依次求解得到的未必就是连续的最大的子数组之和,故此必须在此种情况下也求解出最大子数组之和,方法即是同时从数组的两端依次进行求出各自的最大子数组之和,然后在相遇前求和后与之前所求的最大子数组之和依次相比较,取它们中最大的一个作为连续的最大子数组之和即可。(因为单独从一端所求出的最大子数组之和绝对大于两边同时进行的其中一边所求出的最大字数之和,故保证了程序的非冗余性。)

源代码:

//求一个数组的连续的最大子数组之和
//李敏,Mar 22th
#include <iostream>
using namespace std;
int main()
{
int n, i, j, k,a[1000];
char mm;
do{
cout<<"请输入数组长度:"<<endl;
cin >> n;
for (i=0; i<n; i++)
{
a[i]=-20+rand()%(51);

}
cout<<"系统产生的随机数为:"<<endl;
for (i=0; i<n; i++)
{
cout<<a[i]<<‘\t‘;

}
//依次按数组的顺序求出当前子数组的最大和
int t = a[0];
int sum = t;
for (k=1; k<n; k++)
{
t = max(a[k],t+a[k]);
sum = max(sum, t);
}
//考虑到数组的连续(即数组可形象化为一个圈),故分别从数组首端和末端同时进行以求出两端还未相遇前的各自的最大子数组之和
int s = a[0];
for (i=1; i<n && s+a[i]>s; i++)
s += a[i];
t = a[n];
for (j=n-1; j>=1 && t+a[j]>t; j--)
t += a[j];
//依次比较两端数组还未相遇前的两个最大子数组之和的和与之前按数组顺序求出的最大子数组之和
if (i<j && s+t> sum)
sum = s+t; //取两种情况下的最大字数组之和即可
cout<<"最大字数组之和为:"<<sum<<endl;

cout<<endl;
cout<<"*************************************************************"<<endl;
cout<<" 继续请输入Y 退出请输入N "<<endl;
cout<<"*************************************************************"<<endl;
cin>>mm;
}while(mm==‘y‘||mm==‘Y‘);


}

实验截图:

技术分享技术分享

编程总结:

在此次编程中由于考虑问题的不到位导致本来简单的问题却得不到很好的解决,当遇到问题时借鉴了以下网上相关方面的知识及经验后,自己也找到了自己的设计缺陷,经过类比改正后得到了合理的解决,从解本题可总结出在遇到问题时不要盲目的进行下结论以及上机实验,得多从别人的成功经验之处与自己的思想相比较,只有等思密周全后再去解决问题,而不是去创造更多不能解决的问题,总之站在巨人的肩膀上去解决一切问题才能使自己的思维不断敏捷,成熟,而这才是编程的需要!

项目计划总结:

                                                                      周活动总结表

姓名:李敏                                                                                                    日期:2015/3/22

 技术分享

时间记录日志

学生:     李敏                                                               日期:2015/3/22

教师:     王建民                                                                     课程:软件工程概论

技术分享

缺陷记录日志

学生:李敏

日期:2015/3/22

教员:王建民

程序号:3

技术分享

学生:李敏                                日期:2015/3/22

技术分享

《求一个数组的连续的最大子数组之和》

原文:http://www.cnblogs.com/Twinklelittlestar/p/4357045.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!