設(shè)計思路：

才過幾天就有了新挑戰(zhàn)，我真是找不到多少時間看數(shù)學了，下面是新任務(wù)的大致意思：

輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負數(shù)。數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和，如果數(shù)組A[0]……A[j-1]首尾相鄰，允許A[i-1]，……?A[n-1]，A[0]……A[j-1]之和最大，求最大子數(shù)組的和最大子數(shù)組的位置。

剛開始看這道題，看的我云里霧里的，覺得是看懂了，又感到有些迷惑，所以就簡單把數(shù)組看成環(huán)形，然后想只要循環(huán)兩圈不就解決了嗎！so我開始如下的解題過程

?

求解過程：

這是上次的解題思路：

數(shù)組形式:a[0],a[1],a[2],a[3]........a[n-1],a[n]

總共可以看成求子過程最優(yōu)，共兩種情況：

把b[]=max(a[0]+a[1]+...a[i-1])看成到i元素的(i-1)子數(shù)組最大值

If(b[]<0)這樣a[i]+b[]<a[i]?則最大換為a[i]

If(b[]>=0)a[i]+b[]>a[i]?最大換為a[i]+b[]

基礎(chǔ)上記入頭尾然后再循環(huán)一次，結(jié)束位置在第一次結(jié)束的元素之前一個元素。

?

如下是第一次考慮的錯誤代碼（請不要直接復制）：

?

1 //實現(xiàn)數(shù)組的首尾相連 再求子數(shù)組的和最大值以及子數(shù)組的位置 2 #include<iostream> 3 using namespace std; 4 5 int main() 6 { 7 /*求子數(shù)組的和 8 輸入整形數(shù)組，數(shù)組里有正數(shù)有負數(shù)，連續(xù)數(shù)字構(gòu)成子數(shù)組 9 求子數(shù)組最大值O(n) 10 */ 11 //解題用動態(tài)規(guī)劃求最優(yōu)子結(jié)構(gòu) 12 13 cout<<"請輸入數(shù)組元素個數(shù)："<<endl; 14 int num; //數(shù)組元素個數(shù) 15 cin>>num; 16 int a[100]={0}; 17 for(int i=0;i<num;i++) 18 cin>>a[i]; //輸入數(shù)組元素 19 20 //考慮首尾相連時改變數(shù)組結(jié)束判斷的位置 21 22 //動態(tài)求解 23 int b[100][100]={0}; 24 b[0][0]=0; //初始子數(shù)組和 25 b[0][1]=a[0]; //a[i]數(shù)的值 26 for(int i=1;i<num;i++) 27 { 28 if(b[i-1][0]>=0) 29 b[i][0]=b[i-1][0]+b[i-1][1]; 30 else 31 b[i][0]=b[i-1][1]; 32 b[i][1]=a[i]; 33 } 34 //加上最后一個數(shù)(第一次迭代的結(jié)果) 35 if(b[num-1][0]>=0) 36 b[num][0]=b[num-1][0]+b[num-1][1]; 37 else 38 b[num][0]=b[num-1][1]; 39 b[num][1]=a[0]; //循環(huán)（首尾連） 40 41 //二次迭代 42 for(int i=1;i<num;i++) 43 { 44 if(b[num+i-1][0]>=0) 45 b[num+i][0]=b[num+i-1][0]+b[num+i-1][1]; 46 else 47 b[num+i][0]=b[num+i-1][1]; 48 b[num+i][1]=a[i]; 49 50 } 51 //比較各個子數(shù)組最大的求出值 52 int max=b[0][0]; 53 for(int i=1;i<=(num+num-1);i++) 54 { 55 if(b[i][0]>max) 56 max=b[i][0]; 57 } 58 cout<<"子數(shù)組和最大值為："<<max<<endl; 59 return 0; 60 }

?

可能大家看到這就感覺有問題了，我也感覺有問題，但是說不上，但舉個例子就明白了，

-1，2，3?結(jié)果是6?但答案肯定是5，因為在循環(huán)過程中重復使用數(shù)組元素，所以這樣的算法有問題，得換個思維：

其實這個循環(huán)過程就是每次nun個數(shù)的求解

所以把上述的數(shù)組看成-1?2?3?-1?2,看到這大家的思路肯定更清醒了，只要依次求解每次循環(huán)中子數(shù)組最大，再比較就好了

如下為正確代碼：

?

1 //實現(xiàn)數(shù)組的首尾相連 再求子數(shù)組的和最大值以及子數(shù)組的位置 2 #include<iostream> 3 #include<queue> 4 #include<string> 5 #include<sstream> 6 using namespace std; 7 8 int main() 9 { 10 /*求子數(shù)組的和 11 輸入整形數(shù)組，數(shù)組里有正數(shù)有負數(shù)，連續(xù)數(shù)字構(gòu)成子數(shù)組 12 求子數(shù)組最大值O(n) 13 */ 14 //解題用動態(tài)規(guī)劃求最優(yōu)子結(jié)構(gòu) 15 16 queue<int> q=queue<int>(); //建立隊列來循環(huán)數(shù)組 17 string k[100][100]; //記錄子數(shù)組最大位置 18 cout<<"請輸入數(shù)組元素個數(shù)："<<endl; 19 int num; //數(shù)組元素個數(shù) 20 cin>>num; 21 int a[100]={0}; 22 int i=0,j=0; 23 cout<<"請輸入數(shù)組元素："<<endl; 24 for(i=0;i<num;i++) 25 cin>>a[i]; //輸入數(shù)組元素 26 27 //考慮首尾相連時改變數(shù)組結(jié)束判斷的位置 28 //將n-1個數(shù)組元素放到數(shù)組尾部形成新數(shù)組 29 30 for(j=0;j<num-1;j++) 31 { 32 q.push(a[j]); 33 } 34 for(j=0;j<num-1;j++) 35 { 36 a[num+j]=q.front(); 37 q.pop(); 38 } 39 40 41 //動態(tài)數(shù)組求解 42 int b[100][100][2]={0}; 43 i=0;j=0; 44 for(i=0;i<num;i++) 45 { 46 b[i][0][0]=0; //初始子數(shù)組和 47 b[i][0][1]=a[i]; //a[i]數(shù)的值 48 k[i][0]=""; 49 for(j=1;j<num;j++) 50 { 51 stringstream ss; 52 if(b[i][j-1][0]>=0) 53 { 54 55 b[i][j][0]=b[i][j-1][0]+b[i][j-1][1]; 56 ss<<((i+j-1)%num); 57 ss>>k[i][j]; //寫入位置字符數(shù)組 58 59 k[i][j]=k[i][j-1]+k[i][j]; 60 } 61 else 62 { 63 b[i][j][0]=b[i][j-1][1]; 64 ss<<((i+j-1)%num); 65 ss>>k[i][j]; 66 67 } 68 69 b[i][j][1]=a[i+j]; 70 } 71 stringstream ss; 72 //加上最后一個數(shù) 73 if(b[i][num-1][0]>=0) 74 { 75 b[i][num][0]=b[i][num-1][0]+b[i][num-1][1]; 76 ss<<((i+j-1)%num); 77 ss>>k[i][num]; 78 k[i][num]=k[i][num-1]+k[i][num]; 79 } 80 else 81 { 82 b[i][num][0]=b[i][num-1][1]; 83 ss<<((i+j-1)%num); 84 ss>>k[i][num]; 85 } 86 87 } 88 89 90 //比較各個子數(shù)組最大的求出值 91 int max=b[0][0][0]; 92 int max_i=0; //記錄最大值的坐標 93 int max_j=0; 94 for(i=0;i<num;i++) 95 { 96 for(j=0;j<=num;j++) 97 { 98 if(b[i][j][0]>max) 99 { 100 max=b[i][j][0]; 101 max_i=i; 102 max_j=j; 103 } 104 } 105 } 106 cout<<"子數(shù)組和最大值為："<<max<<endl; 107 108 int si=0,sl=0; 109 cout<<"最大子數(shù)組各元素數(shù)組中的位置為（以0開始）："; 110 if(k[max_i][max_j].size()==1) 111 cout<<k[max_i][max_j]<<endl; 112 else 113 { 114 si=k[max_i][max_j].size(); 115 while(si--) 116 { 117 cout<<k[max_i][max_j][sl++]<<" "; 118 } 119 } 120 cout<<endl; 121 return 0; 122 }

?運行代碼：

求解總結(jié)

看問題必須要通過一些實例的驗證才能確保是正確無誤后，才能正確入手，保證結(jié)果正確性。

最后附上工作照：

Ps:同組的另一戰(zhàn)友的博客

http://www.cnblogs.com/brucekun/p/5321247.html

　　　　每日一小步，月過一大步~~加油

轉(zhuǎn)載于:https://www.cnblogs.com/ly199553/p/5322647.html

總結(jié)

以上是生活随笔為你收集整理的子数组最大值设计02的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。