1.题目要求：求一个二维数组的连通的数组中和最大的最大值。

小组成员：许磊、徐浩军。

方案一：

先将二维数组按正整数数组进行分块，分成若干正数数组块之后，看这几个正数数组块是否联通，若不连通，则需要看将其连同所需要的代价是否合适。

最后再求出最大值。这种方案思路很清晰，但实现起来比较困难，例如，分块的储存（计划用栈或队列进行储存），储存时还要记录每块边缘的坐标以便

与其他正数数组块连通时求出最小代价。后经过讨论，我们选则了方案二。

方案二：

1.按行分组，将二维数组按行分成n个一维数组。

2.求出每个一维数组最大子数组和，并记录最大子数组和的首末位置。（一维数组的最大子数组和算法见上次博客）

3.通过首末位置判断是否联通。如果联通则直接相加，若不连通则需要判断联通所需代价如何。

#include
     
      #include
      
       using namespace std;void MaxIntArray(int a[],int &max,int &begin,int &end,int n);//先将二维数组按行分成n个一维数组，求出每个一维数组最大子数组和，并记录最大子数组和的首末位置，在通过首末位置判断是否联通void main(){           int n,m;//n行m列           cout<<"请输入二维数组的行数和列数："<
       
        >n>>m;           int a[100][100];           int b[100];           cout<<"输入该二维数组"<
        
         >a[i][j];                                  //分块           int Max[100];           int Begin[100];           int End[100];           for(int i=0;i
         
          =Begin[i+1])||(End[i]<=End[i+1]&&End[i]>=Begin[i+1]))                       {                                   max=Max[i+1]+max;                       }                       else                       {                                   //如果不能直接连通，判断代价是否合适                                   if(Begin[i]>End[i+1])                                   {                                       int t = Begin[i]-End[i+1];                                                int s = Begin[i];                                                int temp=0;                                                for(int k=0;k
          
           0) max=temp+Max[i+1]; } if(End[i]
           
            0) max=temp+Max[i+1]; } } } cout<<"最大子数组块的值为："<
            
             <
             
              =Max[j]) { temp=temp+a[i]; Max[j]=temp; if(Bg[j]==-1) Bg[j]=i; Ed[j]=i; i++; } else if(temp+a[i]
              
               0) { temp=temp+a[i]; i++; } else if(temp+a[i]<=0) { i++; j++; Max[j]=0; temp=0; } } max = Max[0]; int q=0; for(int k=0;k<=j;k++){ if(Max[k]>max) { max=Max[k]; q=k; } } begin=Bg[q]; end=Ed[q];}
              
             
            
           
          
         
        
       
      
     

 

实验结果截图：

 

 

实验总结：

1.算法很重要，算法决定了一个程序运行的效率，以及编写代码所需的代码量。只有不断的创新思维才能找到一个问题的优化解。

2.编程前要对程序进行分解，不断细分成几个小问题，只有这样才能将思路缕清。