一、题目要求

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

要求： 输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

            如果数组A[0]……A[j-1]首尾相邻，允许A[i-1]， …… A[n-1]， A[0]……A[j-1]之和最大。 同时返回最大子数组的位置。 

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

 结对编程要求： 两人结对完成编程任务。

                          一人主要负责程序分析，代码编程。 一人负责代码复审和代码测试计划。 

                          发表一篇博客文章讲述设计思想，出现的问题，可能的解决方案（多选）、源代码、结果截图、总结。

二、设计思想

把该环形数组从某一点展开，连写两遍（复制一份接到自己后面），然后当成无环的数组求最大子数组和，但这里要限制一个条件，就是最大子数组的长度不可以超过n，所以求的时候要注意判断。例如：展开写两遍为1 2 3 4 5 1 2 3 4 5.

这种情况下限定最大子数组的长度不可以超过n的作用：假如数组为{-1,2,3,4}，则展开复制一份接到自己后面为-1,2,3,4,-1,2,3,4，此时若直接求则为2,3,4,-1,2,3,4，很明显不对了，所以要限定最大子数组的长度不可以超过n。

三、源程序代码

#include 
      
       #include
       
        #include
        
         #define n 7using namespace std;void main(){    int a[n],i,j,z=0,y[n][n],x1=0,x2=0,t,m;    srand((int)time(0));    //数组的元素值由随机函数产生    for(i=0;i
         
          n-1)            {                m=0;            }            j++;        }    }    t=y[0][0];    for(i=0;i
          
           t)            {                t=y[i][j];                x1=i;                x2=j;            }        }    }    cout<<"最大子数组的值为："<
           
            <
            
             =n) { x1=0; } i++; } cout<
            
           
          
         
        
       
      

 

四、结果截图

五、遇到的困难，解决方法及总结

这次的程序，在我刚刚看到的时候，简直一点思路都没有，所以最后采取的一个同学的思路，在编程的过程中我们还遇到了许多的问题，比如不知道如何把第一个数字移到数组的最后面，后来经过问同学，研究终于得到了解决。还有遇到了闪退的问题，最后是我的小伙伴寻求了外援才解决的。因为有了之前一维数组求最大子数组的经验，这次的实验，在之前的基础上操作，在明确了设计思路，有了编程解决问题的想法之后，显得简单了不少。感觉这次的编程题目主要是这种解决问题的思路值得借鉴。虽然我和我的小伙伴都不太会编程，但是我们还是努力完成了这个题目，也许这就是一点点的进步吧，在以后的过程中，我们会再接再厉，争取能够独立完成一个程序。

六、成员

许兴华   高尉雅