结对开发

1、题目

输出一个整数数组中最大子数组的和。

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

要求时间复杂度为O（n）。

2、设计思路

数组个数可以自己定义，若数组全为负数，则直接比较单个数，求出最大值。输出即可。若有正有负或全为正数则求出相邻正数或相邻负数的和形成正负交替的新数组。

则从正数开始即a[0]或a[1]开始。假如从a[0]开始。若a[0]+a[1]〉=0则将a[2]=a[0]+a[1]+a[2]。同时a[0]存入数组b中，若a[0]+a[1]<0,则将a[0]存入数组b中，

然后继续a[2]+a[3]〉=0比较。以此循环。直至结束。

3、代码

  1 #include<iostream.h>
  2 int main()
  3 {
  4     int N;
  5     cout<<"输入数组个数:";
  6     cin>>N;
  7     int a[20];    //原数组
  8     int b[20];    //正负交替数和
  9     int c[20];    //最终比较数组
 10     int i;
 11     int M;        //存放数组b的长度
 12     int j=0;
 13     int max;      //存放最大值
 14     int p=0;
 15     int sum;      //相邻正数和
 16     int sum1;     //相邻负数和
 17     sum=0;
 18     sum1=0;
 19     int u=0;
 20     //输入数组
 21     for(i=0;i<N;i++)
 22     {
 23         cout<<"输入第"<<i+1<<"个数:";
 24         cin>>a[i];
 25     }
 26     //判断数组是否全负
 27     for(i=0;i<N;i++)
 28     {
 29         if(a[i]>=0)
 30         {
 31             u=1;
 32         }
 33     }
 34     if(u==1)
 35     {
 36         //求出相邻正数或相邻负数的和，形成正负交替数组
 37         for(i=0;i<N;i++)
 38         {
 39             if(a[i]>=0)
 40             {
 41                 if(i<N-1)
 42                 {
 43                     if(a[i+1]>=0)
 44                     {
 45                         sum=sum+a[i];
 46                     }
 47                     else
 48                     {
 49                         b[j++]=sum+a[i]; 51                         sum=0;
 52                     }
 53                 }
 54                 else
 55                 {
 56                     if(a[i-1]>=0)
 57                     {
 58                          b[j++]=sum+a[N-1];
 59                     }
 60                     else
 61                     {
 62                          b[j++]=a[N-1];
 63                     }
 64                 }
 65 
 66             }
 67             else if(a[i]<0)
 68             {
 69                 if(i<N-1)
 70                 {
 71                     if(a[i+1]<0)
 72                     {
 73                         sum1=sum1+a[i];
 74                     }
 75                     else
 76                     {
 77                         b[j++]=sum1+a[i];
 78                         sum1=0;
 79                     }
 80                 }
 81                 else
 82                 {
 83                     if(a[i-1]<0)
 84                     {
 85                         b[j++]=sum1+a[N-1];
 86                     }
 87                     else
 88                     {
 89                         b[j++]=a[N-1];
 90                     }
 91                 }
 92             }
 93         }
 94         M=j;
 95         if(b[0]<0)
 96         {
 97             j=1;
 98         }
 99         else
100         {
101             j=0;
102         }
103         //对数组B进行操作，将利用算法求的机最大值存入数组c中
104         for(int y=j;y<M;y=y+2)
105         {
106             if(y+2<M)
107             {
108                 if(b[y]+b[y+1]>=0)
109                 {
110                     c[p++]=b[y];
111                     b[y+2]=b[y+2]+b[y+1]+b[y];
112                     if((y+2==M-1)||(y+2==M-2))
113                     {
114                         c[p++]=b[y+2];
115                         break;
116                     }
117                 }
118                 else
119                 {
120                     c[p++]=b[y];
121                 }
122             }
123             else
124             {
125                 c[p++]=b[y];
126             }
127 
128         }
129         //对数组c求最大值
130         max=c[0];
131         for(i=0;i<p;i++)
132         {
133             if(c[i]>=max)
134             {
135                 max=c[i];
136             }
137         }
138         cout<<endl;
139         cout<<"最大值max为:";
140         cout<<max<<endl;
141     }
142     else
143     {
144         max=a[0];
145         for(i=0;i<N;i++)
146         {
147             if(a[i]>=max)
148             {
149                 max=a[i];
150             }
151         }
152         cout<<"最大值max为:";
153         cout<<max<<endl;
154     }
155     return 0;
156 }

四、运行截图

五、心得体会

此次是结对开发，本来思路不统一，一个想用这个算法，一个用求出所有子数组的方法，经过商讨，最终决定以此方法来进行。

过程中他提醒我数组边界等等的考虑，我想如果没有这句话。整个程序应该是崩溃的。还有就是多方面的思路让这个程序可以适应

任意数组。我们同感觉这程序缺点就是没有模块化，像应该写成函数形式的没有写成。导致程序不系统化。这是我们应该改正的，

结对开发明显和自己单独编程是不一样的。我们需要相互的提醒，避免了好多错误。三人行必有我师。合作才能共赢。初次与他合作

还有些不太适应。不过在以后的合作中必将成功。

六、我们的合照。