syamphanindra7's blog

Can anyone explain the solution that i found for this question or even a better solution if u can??
By syamphanindra7, history, 7 years ago, In English

https://www.codechef.com/problems/MXSUBMT

int main() {

ios::sync_with_stdio(false);
int n,m;
cin >> n >> m;
int a[n][m];
for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++){
        cin >> a[i][j];
    }
}

ll ans = -10000;
for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++){
        for (int i1 = i; i1 < n; i1 ++){
            for (int j1 = j; j1 < m; j1 ++){
                ll cur = 0;
                for (int k = i; k <= i1; k++){
                    for (int l = j; l <= j1; l++){
                        cur += a[k][l];
                    }
                }
                ans = max(ans,cur);
            }
        }
    }
}
cout << ans << endl;

}

  • Vote: I like it
  • -13
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The code seems pretty clear: for every submatrix with the top-left corner at (i,j) and the bottom-right corner at (i1,j1) compute the sum in O(n^2) and update the answer.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there more better way to find this??

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, there are better ways. The above code takes O(n^6) time. It can be done in O(n^3), by using a combination of Kadane's algorithm and prefix-sum-arrays. You can find a short explanation and an implementation here. However you should make yourself familiar with the two concepts, before you visit that link.

    → Reply