一、题目要求

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

　　要求：

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

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

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

　　结对编程要求：

　　　　两人结对完成编程任务。

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

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

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

二、算法思想

　　　　改程序本身并不是很难，一般来讲，用for循环就可以根据输入打印所求的值，但是对于要求时间复杂度是o(n),

　　就不能单纯的用for嵌套来实现了。所以用的是取数组的中间的值，对左右依次求最大值，并对左右各部分再求最大值，运用递归最后实现算法要求。

　　在这个程序中，主要的算法思想是有我的同伴想出来并编写的的，而我只负责测试数据。

三、源代码

　　

# include 
     
      #define LENGTH 5                                //定义出数组的长度using namespace std;//求两个数字的最大值int Max(int  a,int  b,int c){    int temp = a>b?a:b;    int max = temp>c?temp:c;    return max;}//求最大子数组的和int SelectMaxArr(int  arr[],int left,int right){    if(left == right)                                    //嵌套结束条件    {        return arr[left];    }    int maxMidLeft,maxMidRight;                //存放包含中点的左右部分的最大值    int TempLeft,TempRight;                    //存放中点左右部分的最大值    int maxLeft,maxRight;                        //存放最终该嵌套层中左右部分的最大子数组的和    int mid;                                                //存放每次嵌套的中点    mid = (left+right)/2;    maxMidLeft = arr[mid];                    //初始化为边界值    maxMidRight = arr[mid+1];                //初始化为边界值（否则会出现负数组最小为0的问题）    TempLeft = 0;    TempRight = 0;    for(int i = mid;i >= left;i--)                //从中点作为边界开始求其两边最大的子数组并依次递归(左侧部分)    {        TempLeft += arr[i];        if(maxMidLeft < TempLeft)        {            maxMidLeft = TempLeft;        }    }    for(int i=mid+1;i<=right;i++)            //从中点作为边界开始求其两边最大的子数组并依次递归(右侧部分)    {        TempRight += arr[i];        if(maxMidRight < TempRight)        {            maxMidRight = TempRight;        }    }    //递归计算左右两部分的最大子数组的和    maxLeft = SelectMaxArr(arr,left,mid);    maxRight = SelectMaxArr(arr,mid+1,right);    return Max(maxLeft,maxRight,maxMidLeft+maxMidRight);}//测试函数int main(){    int Arr[LENGTH];    int max;                    //存放最大子数组的和    cout<<"请输入"<
      
       <<"个整数(可正可负):";    for(int i=0;i
       
        >Arr[i];    }    max = SelectMaxArr(Arr,0,LENGTH-1);    cout<<"该数组中最大子数组的和为:"<
        
         <
        
       
      
     

 

　　

四、运行截图

　　

五、总结

　　　　时间复杂度是对程序的重要规定，这就不能在用for的嵌套来实现了。所以用到了递归，可能还有别的方法，希望有其他方法的人指教。