结对成员：信1201-1班 黄亚萍
信1201-1班 袁亚姣
一、题目要求
题目:返回一个整数数组中最大子数组的和。
要求：
要求程序必须能处理1000 个元素；
每个元素是int32 类型的；
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
二、设计思路
当对1000个数的数组求最大子数组的和，若随机生成的数溢出，则结束该程序。
三、源程序代码
1 // jie.cpp : Defines the entry point for the console application.
2 //
3
4 #include "stdafx.h"
5 #include "stdlib.h"
6 #include"iostream.h"
7 #include"math.h"
8 #include"time.h"
9 # define N 10000
10 int sum1(int k,int a[],int number)
11 {
12 int x=0;
13 for(int i=k;i<=number+k-1;i++) //数组维数为number
14 {
15 x=x+a[i];
16 }
17 return x;
18 }
19 int Largest(int list[],int length)
20 {
21 int sum[N],max1[N];
22 int i,max;
23 for(i=1;i<=length;i++) //元素个数为i
24 {
25 cout<<"子数组中元素的个数数为"<<i<<"时，子数组的和的最大值为";
26 for(int j=1;j<=length-i+1;j++) //子数组的第j个元素,求最大值
27 {
28
29 sum[j]=sum1(j,list,i);
30
31 if(sum[j]>=max1[i])
32 {
33 max1[i]=sum[j];
34 }
35 }
36 cout<<max1[i]<<endl;
37 }
38
39 max=max1[1];
40 for(int k=1;k<=length;k++)
41 {
42 if(max1[k]>=max)
43 {
44 max=max1[k];
45 }
46 }
47 return max;
48 }
49
50 int main(int argc, char* argv[])
51 {
52 int i,number;
53 int max;
54 srand( (unsigned)time( NULL ) );
55 cout<<"输入这组数的个数：";
56 cin>>number;
57 cout<<endl;
58 int list[N];
59 cout<<"输入这组数："<<endl;
60 for(i=1;i<=number;i++)
61 {
62 cout<<"第"<<i<<"个数:";
63 list[i]=rand()%12345678912345678934+2147483646;
64 if(list[i]<0)
65 {
66 cout<<"数据溢出"<<endl;
67 exit(0);
68 }
69 else
70 {
71 cout<<list[i];
72 }
73
74 cout<<endl;
75 }
76 cout<<"最大值为:"<<Largest(list,number)<<endl;
77 cout<<endl;
78 return 0;
79 }
四、运行结果
五、总结与心得
本次实验是我们结对开发以来实验完成的最不理想的一个，对数据溢出只进行了溢出的判断，若溢出则结束程序，未能继续运行程序。
