合作项目3

结组成员：信1201-1柴珏辉信1201-2邓锐

一、要求

1、题目:

返回一个整数数组中最大子数组的和。

2、要求：

要求程序必须能处理1000 个元素；

每个元素是int32 类型的；

输入一个整形数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

3、结对开发要求:

两人结对完成编程任务。

一人主要负责程序分析，代码编程。

一人负责代码复审和代码测试计划。

发表一篇博客文章讲述两人合作中的过程、体会以及如何解决冲突(附结对开发的工作照)。

二、设计思路

通过数组的首尾两个位置定位子数组，找出首尾两位置的所有组合，即找出了所有可能的子数组，并计算它们的和，找出最大值。

查找资料得知，对于64位处理器，int与int32类型相同，最大均是2的31次方（有符号整数）。时间复杂度要求未实现。

三、程序代码

 1 #include<iostream.h>
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<time.h>
 5 #define N 1000
 6 int qiuhe(int a[],int i,int j)   //求数组的和
 7 {
 8     int he=0,b;
 9     for(b=i;b<=j;b++)
10     {
11         he=he+a[b];
12     }
13     return he;
14 }
15 void show(int a[],int i,int j )  //显示形式
16 {
17     int b;
18     for(b=i;b<=j;b++)
19     {
20         if(b%20==0)
21         {cout<<endl;}
22         cout<<a[b]<<" ";
23     }
24     cout<<endl;
25 }
26 void main()
27 {
28     int yuan[N];  //定义数组，保存随机生成的数
29     int i,j,ra,p=0,shu1,shu2,max;
30     srand((unsigned)time(NULL));
31     for(i=0;i<N;i++)
32     {
33         yuan[i]=(rand()-10000)*100;
34     }
35     i=0;
36     j=0;
37     max=yuan[0];
38     shu1=0;
39     shu2=0;
40     for(i=0;i<N;i++)        //找最大值
41     {
42         for(j=i;j<N;j++)
43         {
44             if(qiuhe(yuan,i,j)>max)
45             {
46                 max=qiuhe(yuan,i,j);
47                 shu1=i;
48                 shu2=j;
49             }
50         }
51     }
52     if(max<2100000000)    //大数处理 int最大值为2的31次方
53     {
54         cout<<"原数组：";
55         show(yuan,0,N-1);
56         cout<<"最大子数组：";
57         show(yuan,shu1,shu2);
58         cout<<"最大值：";
59         cout<<max<<endl;
60     }
61     else
62     {
63         cout<<"最大数超出类型所能表示的最大数，溢出"<<endl;
64     }
65 
66 }

截图：

四、测试

1.N=10000，5000时没有显示

N=2000,3000时可以实现

N=3000

2.生成随机数范围yuan[i]=(rand()-10000)*10000000，超出2的31次方，溢出

五、心得体会

int32类型不清楚，查资料了解了一下int与int32类型。合作上没有问题。

结组成员照片：