/*于計算最大子矩陣和問題*/
#include <iostream>
#include <fstream>
using namespace std;
    
int **Maxtrix; 
int Sum1(int,int*); //定義單行數組
int Sum2(int,int,int **); //定義矩陣數組
int Sum1(int n,int *a)  //定義單行數組取最大和函數
{   
    int sum=0;
	int b=0,i;
	for (i=1;i<=n;i++)
	{
	  if(b>0) b+=a[i];
	  else b=a[i];
	  if(b>sum) sum=b;
	}
	return sum;
}
int Sum2(int m,int n,int **a) //定義矩陣數組取最大和函數
{
	int sum=0;
	int *b,i,j;
	b=new int[n+1];
  
	for(j=1;j<=n;j++) b[j]=0; //初始化數組
	for(i=1;i<=m;i++)
	{
	  for(j=1;j<=n;j++) 
	  b[j]+=a[i][j];  //向下合并數據
	  int max=Sum1(n,b);
	  if (max>sum) sum=max;
	}
	delete[] b;
	return sum;
}
//主函數
int main()
{  
  int m,n,i,j;
  ifstream in("input.txt"); //打開輸入文件input.txt
  if (in.fail())
  {
  	cout<<"the input.txt is not exist!";
	exit(1);
  }
  in>>m>>n;
  if ((m<=0)||(n<=0))
  {
	cerr << "輸入錯誤數據！";
    exit(1);
  }

//順序讀入矩陣的元數
Maxtrix=new int* [m+1];
for (i=0;i<=m;i++)
{
  if (!(Maxtrix[i] = new int[n+1]))
  { 
  //內存分配不成功，退出
	cout<<"Memory Allocation Error!"<<endl;
	exit(1) ;
  }
}
for(i=1;i<=m;i++)
  for(j=1;j<=n;j++)
	{ in>>Maxtrix[i][j]; }
  ofstream out("output.txt"); //創建輸出文件output.txt
  out<<Sum2(m,n,Maxtrix);
  return 1;

//刪除動態數組
delete[] *Maxtrix;
}