maximum_2d_sum.cpp

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
int countI;
int countDP;
int countKadne;

int maxSizeIter(vvi elems, int t){
  int maxSize = INT_MIN;
  for(int i = 0; i != t; ++i){
    for(int j = 0; j != t; ++j){
      for(int k = i; k != t; ++k){
        for(int l = j; l != t; ++l){
          int sizeRect = 0;
          for(int a = i; a <= k; ++a){
            for(int b = j; b <= l; ++b){
              countI++;
              sizeRect += elems[a][b];
            }
          }
          maxSize = max(maxSize, sizeRect);
        }
      }
    }
  }
  return maxSize;
}

int maxSizeDP(vvi elems, int t){
  for(int i = 0; i != t; ++i){
    for(int j = 0; j != t; ++j){
      if(i>0) elems[i][j] += elems[i-1][j];
      if(j>0) elems[i][j] += elems[i][j-1];
      if(i>0 && j>0) elems[i][j] -= elems[i-1][j-1];
    }
  }

  int maxSize = INT_MIN;
  for(int i = 0; i != t; ++i){
    for(int j = 0; j != t; ++j){
      for(int k = i; k != t; ++k){
        for(int l = j; l != t; ++l){
          int sizeRect = elems[k][l];
          countDP++;
          if(i>0) sizeRect -= elems[i-1][l];
          if(j>0) sizeRect -= elems[k][j-1];
          if(j>0 && i>0) sizeRect += elems[i-1][j-1];
          maxSize = max(maxSize, sizeRect);
        }
      }
    }
  }
  return maxSize;
}

int find_max(vi &elems, int t){
  int max_val = 0, ans = 0;
  for(int i = 0; i != t; ++i){
    countKadne++;
    max_val += elems[i];
    if(max_val > 0)
      ans = max(max_val, ans);
    else
      max_val = 0;
  }
  return ans;
}

int maxSizeKadne(vvi elems, int t){
  vi tmp(t, 0);
  int ans = 0;
  for(int l = 0; l != t; ++l){
    tmp = elems[l];
    ans = max(ans, find_max(tmp, t));

    for(int r = l+1; r != t; ++r){
      for(int i = 0; i != t; ++i){
        tmp[i] += elems[r][i];
      }
      ans = max(ans, find_max(tmp, t));
    }
  }
  return ans;
}


int main(){
  ios::sync_with_stdio(false);
  int t;
  freopen("test.in", "r", stdin);
  cin >> t;
  vvi elems(t, vi(t, 0));
  countI = 0;
  countDP = 0;
  for(int i = 0; i != t; ++i){
    for(int j = 0; j != t; ++j){
      cin >> elems[i][j];
    }
  }

  cout << "Iter method       ans => " << maxSizeIter(elems, t)
       << " loop ran => " << countI << endl;
  cout << "DP                ans => "<< maxSizeDP(elems, t)
       << " loop ran => " << countDP << endl;
  cout << "Kadne(DP+greedy)  ans => "<< maxSizeKadne(elems, t)
       << " loop ran => " << countKadne << endl;
  return 0;
}

output.txt

Iter method       ans => 15 loop ran => 400
DP                ans => 15 loop ran => 100
Kadne(DP+greedy)  ans => 15 loop ran => 40

test.in

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2