結對成員：

朱少輝：主要負責代碼編寫

侯濤亮：主要負責程序測試

題目:一個首尾相接的一維整型數組，其中有正有負，求它的最大子數組并返回它的位置。

思路：在求一維子數組的基礎上，先輸入一個含有N個數的一維數組，將此數組向后平移N個使數組長度變為2N個，前N個和后N個值相等。再求這長度為2N的數組最大子數組之和，也就是求從第i個(i=0,1,2..n-1)到第i+n(不包含i+n）個中求最大的子數組和。這樣會從0-N-1產生產生N個最大子數組的和，把這N個值存到另個數組中，求出最大值即為首位銜接一維子數組的最大值。該算法的時間復雜度為o(n^2）。

代碼：

#include<iostream> #include<cmath> using namespace std; void main() {int a[25000],i,j,n,MaxSum,k,m,h,p;int f=0;int b[10],d[10];cout<<"請輸入數組中數字的個數"<<endl;cin>>n;cout<<"請輸入數組"<<endl;for(i=0;i<n;i++){cin>>a[i];}for(i=n;i<2*n;i++){a[i]=a[i-n];}cout<<endl;for(i=0;i<n;i++){k=0;MaxSum=0;h=i;for(j=i;j<i+n;j++){k += a[j];if(k > MaxSum){ MaxSum = k;h=j;}if(k < 0){k = 0;}}d[i]=h;b[i]=MaxSum;}int c=b[0];m=0;h=0;for(i=1;i<n;i++){if(c<=b[i]){c=b[i];m=i;h=d[i];}}p=h-n+1;if(p<=0){ p=n;}cout<<"從第"<<m+1<<"個到第"<<p<<"個"<<endl;cout<<"最大子數組為"<<endl;for(i=m;i<h+1;i++){ cout<<a[i]<<" ";}cout<<endl;cout<<"最大子數組之和為"<<c<<endl;}

截圖

總結：這次的程序是上次程序的進化，具體思路還是一樣的。由此可見許多程序的算法都是有關聯的，我們要學會繼承和創新。此外結對開發過程中，隊友之間的配合，溝通，交流和信任也是十分重要的。通過幾次的合作我們都有了很大的進步。

轉載于:https://www.cnblogs.com/bingoing/p/4421671.html

總結

以上是生活随笔為你收集整理的求首位相连一维数组最大子数组的和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。