求二维数组中子数组和中最大的值，及子数组

个人信息：就读于燕大本科软件工程专业 目前大三;

本人博客：google搜索“cqs_2012”即可;

个人爱好：酷爱数据结构和算法，希望将来从事算法工作为人民作出自己的贡献;

编程语言：C++ ;

编程坏境：Windows 7 专业版 x64;

编程工具：vs2008;

制图工具：office 2010 powerpoint;

硬件信息：7G-3 笔记本;

真言

每次着急写程序，碰到问题就头疼，头疼之后便是满满的收获，付出总有回报。

求二维数组中子数组和中最大的值，及子数组

方案

我们已经做过一维数组的问题。如果你没有看过一维数组的问题，请戳 求子数组之和最大值

二维数组是一维数组的数组，这样理解起来，我们就不费事了

我的算法是先将压缩列，即每一列的和作为新数组的元素来组成新的数组来简化问题，然后就变成一维数组求最大子数组问题了

具体算法设计用C++表示如下

// 求出二维数组的最大子二维数组
	int Array::Max_Sum_Sub_Double_Array(int **data,const unsigned int row,const unsigned int column)
	{
	// 异常输入
		if(data == NULL || row == 0 || column == 0)
		{
			cout<<"异常输入 Max_Max_Sub_Double_Array"<
   
     column || s>e || e>row)
		{
			cout<<"异常输入 Sum_Sub_Column_Double_Array"<
    
      row || s>e || e> column) { cout<<"异常输入 Sum_Sub_Row_Double_Array"<
     
      = 0 ) { all_fushu = false ; break ; } else if( data[i] > data[max] ) { max = i ; } } // 如果都是负数 if(all_fushu == true) { R = L = max+1; return void(0); } // 如果不都是负数 else { // 核心算法 初始化 int left_sum = data[0],right_sum = data[length-1] ; int left = 0,right =length-1; L = left; R = right ; // 选择前进方向 while(left < right-1) { if(left_sum < right_sum) { if(left_sum < 0) { left_sum = 0 ; L = left+1 ; } left++; left_sum += data[left]; } else { if(right_sum < 0) { right_sum = 0; R = right -1; } right--; right_sum += data[right]; } } // 寻求结果 // 如果舍弃左半个数组，保留右半个数组 if(left_sum <= 0) { L = right + 1; R++ ; } // 如果舍弃右半个数组，保留左半个数组 else if(right_sum <= 0){ L++; R = left+1; } // 两边都不舍弃 else{ L++;R++; } return void(0); } } }