一、题目要求

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

  要求：

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

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

  如 果数组A[0]……A[j-1]首尾相邻，允许A[i-1]， …… A[n-1]， A[0]……A[j-1]之和最大。

  同时返回最大子数组的位置。

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

 

二、设计思路

  这次的设计思路还是沿用第一次的一位数组的算法寻找最大值，不过这次的主要问题在于这次的一位数组要首尾相连，允许A[i-1]， …… A[n-1]， A[0]……A[j-1]之和最大，所以我们采用以下方法寻找最大值

  如输入 a1 a2 a3 a4这4位数，我们将其扩展为

            a1 a2 a3 a4 a1 a2 a3

然后调用函数找出最大子数组的和（这里利用的方法和第一次一维数组的方法相同），并返回这个最大子数组

 

三、源程序

 

1 //结对人员：盖相庚  曹美娜 2 //开发时间：2015/3/27 3  4 #include "stdio.h" 5 #include"stdlib.h" 6 #include"time.h" 7 #define N 1000  8 int compare( int arry[],int length) 9 {10     int max[N],max1;11     int maxlocat[N];12     for(int j=0;j<(length+1)/2;j++)13     {14         int sum=0;15         max1=-9999999;16         int z=0;17         for(int i=j;i<(length+1)/2+j;i++)18         {19             sum=sum+arry[i];20             if(sum>=max1)21             {22                 max1=sum;23                 z++;24             }25         }26         max[j]=max1;27         maxlocat[j]=z;28     //    printf("包含数组中第%d个数的所有子数组中和最大的值为:%d\n",j+1,max[j]);29     }30     int fmax=max[0];31     int q=0;32     for(int i=0;i<(length+1/2);i++)33     {    34         if(max[i]>fmax)35         {36             fmax=max[i];37             q++;38         }39     }40 41     int locat=maxlocat[q];42 43     printf("最大子数组为：\n");44     for(int num=q;num

 

四、截图

发现输出结果错误

后经调试发现

改正为

改正后的输出结果为

五、结对心得

  此次上面的内容我还是照搬的娜姐的上去了。。。毕竟主程序什么的都是娜姐写上去的所以还是诚实点好。。娜姐帮了很大的忙...我老是出去玩所以每次都是娜姐找我表示很抱歉。。以后还会努力像娜姐学习，努力努力~~~谢谢娜姐 谢谢老湿~~~~~~~~~~~么么哒

六、工作照

好吧照片还是上一次的，是因为我把新拍的给整丢了，老师你可别怪我啊