1 问题：返回一个二维整数数组中最大联通子数组的和

2 思路：对n*m的二维数组进行分解，分解为n个一维数组，再先求这n个一维数组的最大子数组和，并记下每行最大一维子数组的下标如2-5，这是就会分两种情况第一种是行之间的最大子数组是相连的，如第一行是2-5，第二行是3-6，这是直接相加就行。第二种是不相连的如第一行是2-5，第二行是6-7，这时候就把每行的最大子数组看成一个整体，再使每个最大数组块进行相连，求使其相连的最小代价。最后就可求出最大联通子数组的和。

3 代码

1 #include
     
       2 using namespace std; 3 int zuida(int n,int a[],int *sm,int *mm); 4  5 void main() 6 { 7     int m,n,i,j,sm,mm,t2; 8     int sum,max; 9     int up[100],down[100],t[100];10     int a[100][100],b[100];11     cout<<"输入二维数组的行"<
      
       >m;13      cout<<"输入二维数组的行"<
       
        >n;15     for(i=0;i
        
         >a[i][j];20         }21     }22  23     for(i=0;i
         
          =up[i+1])39         {40             t2+=t[i+1];41         }42          for(j=up[i];j
          
           0) t2+=a[i+1][j]; //判别独立正数45 }46 47 }48 cout<
           
            <
            
             = 0;i--)79 {80 if (b[i] == a[i])81 {82 *sm= i;83 break;84 }85 }86 return max1;87 }88
            
           
          
         
        
       
      
     

4 截图

 

5 总结：我感觉这次题目要比上次题目难，难点就在于使每行最大子数组的相连，因为不是直接相连就能得到最大值，还要进行判断比大小，就像数据结构中的求最短路径问题，使用迪杰斯特拉算法。程序永远都是不同模块的组合，编程时要一步一步的实现每个功能模块，是复杂程序简单化，逐个击破。