结对开发首尾相接数组求子数组最大和

组员：燕亚峰  20122914  

        王童博   20122823

一、题目及要求：

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

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

二、设计思路：

      对于这题本想延用一维数组的方法，不过由于数组进行了整合，始末位置无法判断。所以此种方法断然没有实现。

      可以形成一个固定长度的窗口，依次相加比较。

      首先将为两种情况，一种是跨越a[n-1]，a[0]的。一种是没有跨越的。

      对于没有跨越的，方法很多。对于跨零点的，则可以转换成求其子数组最小和。由于数组总和确定。对于中间那段必定为最小和。总和减最小和求出最大和。对于两个最大和进行比较。得到最终结果。

三、代码

#include
#include
struct ret
{int max,start,end;       //用于存放最大值，及始末位置
};struct ret max2(int arry[],int length)  //跨越arry[n-1]、arry[0]的最大和
{int total=0;int start1=0;int start2;    //起始位置int end=0;int sum=arry[0];int minsum=arry[0];for(int i=1;i){if(sum>0){sum=arry[i];start1=i;}else{sum=sum+arry[i];}if(minsum>=sum){minsum=sum;end=i;start2=start1;}total=total+arry[i];}total=total+arry[0];minsum=total-minsum;struct ret ret1={minsum,start2,end};return ret1;
}struct ret max1(int arry[],int length)   //不跨越零点的最大和
{int start1=0;int start2;     //起始位置int end=0;int sum=arry[0];int maxsum=arry[0];for(int i=1;i//求出相邻数组最小和
    {if(sum<0){sum=arry[i];start1=i;}else{sum=sum+arry[i];}if(maxsum<=sum){start2=start1;end=i;maxsum=sum;}}struct ret ret1={maxsum,start2,end};return ret1;
}int main()
{srand((unsigned)time(0));int N;cout<<"输入元素个数:";cin>>N;int a[20];for(int i=0;i){a[i]=rand()%20-10;cout<"  ";}cout<<endl;struct ret w=max2(a,N);   //调用max2函数，求跨越零点的最值struct ret q=max1(a,N);if(w.max>q.max){cout<<"最大和为:"<"起始位置:"<1<<"结束位置:"<1;}else{cout<<"最大和为:"<"起始位置:"<"结束位置:"<<q.end;}return 0;
}

四、截图

五、实验总结

通过这次试验我发现我们的合作越来越默契了，我们交流沟通也在很愉快的气氛中进行，以前都是吵吵闹闹的。这次试验有两种情况，一种是跨越a[n-1]，a[0]的，一种是没有跨越的。对于没有跨越的，方法很多。对于跨零点的，可以转换成求其子数组最小和。由于数组总和确定。对于中间那段必定为最小和。总和减最小和求出最大和。对于两个最大和进行比较，得到最终结果。

六、合照

转载于:https://www.cnblogs.com/yanyafeng/p/4378789.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！