结对成员:范德一,赵永恒
一.题目:
返回一个整数数组中最大子数组的和。
二.要求:
要求程序必须能处理1000 个元素;
每个元素是int32 类型的;
输入一个整形数组,数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求所有子数组的和的最大值。
三.设计思路
在上一次的实验中,我们设置的数组的个数能够很好的进行扩展,所以对于第一个要求处理1000个元素比较容易实现;对于第二个要求,我们主要是想确定最大的数到底有多大,即什么时候会发生溢出的问题,当问题出现时程序怎么处理,通过查阅资料,我们最后确定了程序能够处理的最大数的取值,然后通过输出语句提示数组溢出。
四.源代码
#include<iostream.h> #include<time.h> #include<stdlib.h> int main() { srand((unsigned)time(NULL)); int a[1000]; int m; //m是每组个数 int *sum=new int[1000]; cout<<"*********************************"<<endl; for(int i=0;i<1000;i++) { int b; b=rand()%2; switch (b) { case 0: a[i]=rand()*350; break; case 1: a[i]=-rand()*100; break; } cout<<a[i]<<" "; if((i%10)==9) cout<<endl; //每行10个输出,换行 } cout<<"*********************************"<<endl; int he=0; for(m=1;m<1001;m++) { int temp=0; for(int n=0;n<m;n++) { temp=temp+a[n]; } for(int k=0;k<=(1000-m);k++) { sum[k]=0; for(int j=k;j<(k+m);j++) //a[k]是每组第一个数 { sum[k]=sum[k]+a[j]; } if(sum[k]>temp) { temp=sum[k]; } } if(temp>he) { he=temp; } } if(he>2100000000) { cout<<"数组溢出!"<<endl; } else { cout<<"最大子数组的和为: "<<he<<endl; } cout<<"*********************************"<<endl; return 0; }
五.运行截图
附:
原文:http://www.cnblogs.com/myblog1993/p/4376510.html