#include <iostream> using namespace std ;

//一维最大子段和问题：动态规划

int MaxSum( int n, int *a) {  int sum = 0, b = 0;  for( int i = 0; i < n; i++ )  {   if(b > 0) b+= a[i] ;   else b = a[i] ;   if(b>sum) sum = b ;  }  return sum ; }

//二维最大字段和问题：动态规划

int MaxSum2( int r, int c, int **a) {  int sum = 0, max;  int *b = new int[c] ;  for( int i=0; i < r; i++)  {   for(int k=0; k < c; k++) b[k] = 0;   for(int j=i; j < r; j++)   {    for( int k=0; k < c; k++) b[k] += a[j][k] ;    max = MaxSum(c, b) ;    if(max > sum) sum = max ;   }  }  return sum ; }

int main()

{  int *a, **b ;  int al, br, bc ;  cout << "请输入一维数组的长度和数据: " << endl ;  cin >> al ;  a = new int[al];  for(int i=0; i < al; i++) cin >> a[i] ;  cout << "一维最大字段和： " << MaxSum(al,a) << endl;  cout << "请输入二维数组的行数、列数和数据：" << endl ;  cin >> br >> bc ;  b = new int*[br] ;  for(int i=0; i<br; i++)  {   b[i] = new int[bc] ;  }  for(int j=0; j < br; j++)  {   for(int i=0; i<bc; i++)   {    cin >> b[j][i] ;   }  }  cout << "二维最大字段和：" << MaxSum2(br, bc, b) << endl ;  for(int i=0; i<br; i++)  {   delete []b[i] ;   b[i] = NULL ;  }  delete []b ;  b = NULL ;  return 0 ; }