這次是求聯(lián)通子數(shù)組的求和，我們想用圖的某些算法，比如迪杰斯特拉等，但是遇到了困難。用BFS搜索能達(dá)到要求，但是還未能成功。

??? 那么我們這樣想，先將每行的最大子數(shù)組之和，然后再將這些最大之和組成一個(gè)數(shù)組，在進(jìn)行求和，這樣就保證了，加入中間一行為負(fù)數(shù)，再進(jìn)行篩選。增加了直接相加的正確率。

??? 實(shí)現(xiàn)代碼：

#include <iostream> #include <fstream> using namespace std; int Max(int Array[],int length) { int maxSumOfArray,maxSum; int first=0,last=1; maxSumOfArray=maxSum=Array[0]; //當(dāng)我們加上一個(gè)正數(shù)時(shí)，和會(huì)增加；當(dāng)我們加上一個(gè)負(fù)數(shù)時(shí)，和會(huì)減少。 //如果當(dāng)前得到的和是個(gè)負(fù)數(shù)，那么這個(gè)和在接下來(lái)的累加中應(yīng)該拋棄并重新清零，不然的話這個(gè)負(fù)數(shù)將會(huì)減少接下來(lái)的和。 for(int i=1;i<length;i++) { maxSumOfArray=max(maxSumOfArray+Array[i],Array[i]); //變量maxSumOfArray 為包含Array[i] 與Array[i] 取最大 maxSum=max(maxSum,maxSumOfArray); ////變量maxSum 為maxSum 與 maxSumOfArray 取最大 } cout<<"最大子數(shù)組和："<<maxSum<<endl; return maxSum; } int main() { int a; int i=0,j=0; int b[10][10],c[10]; FILE * fp1 = fopen("E:\\input.txt", "r");//打開(kāi)輸入文件 if (fp1==NULL) {//若打開(kāi)文件失敗則退出 puts("不能打開(kāi)文件！"); return 0; } int M,N; fscanf(fp1,"%d",&a); M=a; //行 cout<<"行數(shù):"<<M<<endl; fscanf(fp1,"%d",&a); N=a; //列 cout<<"列數(shù):"<<N<<endl; for (i=0;i<M;i++) { for(j=0;j<N;j++) { if(fscanf(fp1,"%d",&a)==1) { b[i][j]=a; cout<<b[i][j]<<" "; } } cout<<endl; } cout<<"文件已經(jīng)讀取到第 "<<ftell(fp1)<<" 個(gè)偏移字節(jié)"<<endl;//輸出fp1指針當(dāng)前位置相對(duì)于文件首的偏移字節(jié)數(shù) fclose(fp1);//關(guān)閉輸入文件 int thismax[10]; //存放數(shù)組每行的最大子數(shù)組 cout<<"每行的最大數(shù)組和："<<endl; for(i=0;i<M;i++) { for(j=0;j<N;j++) { c[j]=b[i][j]; } thismax[i]=Max(c,N); } cout<<"每行的最大子數(shù)組之和再求和"<<endl; int sum=Max(thismax,M); //每行作為一個(gè)數(shù)組再求最大的子數(shù)組和 cout<<"最大聯(lián)通子數(shù)組的和為："<<sum<<endl; return 0; }

這種方法只能在某些情況下可以實(shí)現(xiàn)，更加完整的我們還在完善。

隊(duì)友 于磊http://www.cnblogs.com/cnyulei/

轉(zhuǎn)載于:https://www.cnblogs.com/L-Damon-v/p/5360829.html

總結(jié)

以上是生活随笔為你收集整理的最大连通子数组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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