POJ ( acm.pku.edu.cn ) 1050

把二维的拍扁成一维的，然后谁都会做了。

#include <iostream>
using namespace std;
__int64 max_sum(int* array, size_t len){
__int64 m=-0x7fffffff, mx=-0x7fffffff;
for ( size_t i=0;i<len;++i) {
   if ( mx>=0 ) mx+=array[i];
   else if (mx<array[i]) mx=array[i];
   if(mx>m) m=mx;
}
return m;
}
template <class T>
__int64 max_sum_2d(T matrix, size_t len){
__int64 m=-0x7fffffff,t;
for(int i=0;i<len;++i){
   int tmparr[100]={0};
   for(int j=i;j<len;++j){
       for(int k=0;k<len;++k)
           tmparr[k]+=matrix[j][k];
       t=max_sum(tmparr,len);
       if(t>m) m=t;
   }
}
return m;
}

int main() {
int matrix[100][100];
for(int n;cin>>n;){
   for(int i=0;i<n;++i)
       for(int j=0;j<n;++j)
           cin>>matrix[i][j];
   cout<<max_sum_2d(matrix,n)<<endl;
}
return 0;
}

对了还有神奇的事情就是把函数头改了改之后他算出来的答案就很无厘头了：

有人知道为什么吗？

template <class T,int len>
__int64 max_sum_2d(T (&matrix)[len][len]){
  __int64 m=-0x7fffffff,t;
  for(int i=0;i<len;++i){
      int tmparr[len]={0};
      for(int j=i;j<len;++j){
          for(int k=0;k<len;++k)
              tmparr[k]+=matrix[j][k];
          t=max_sum(tmparr,len);
          if(t>m) m=t;
      }
  }
  return m;
}