Se dă o matrice de numere întregi cu n linii și n coloane.

Cerința

Să se determine suma maximă care se poate obține dintr-o submatrice.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi elementele matricei cu n linii și n coloane.

Date de ieșire

Programul va afișa pe ecran suma maximă care se poate obține dintr-o submatrice.

Restricții și precizări

• 1 ≤ n ≤ 300
• Elementele matricei sunt numere întregi din intervalul [-1000, 1000]
• O submatrice poate fi formată dintr-un singur element

Exemplu

Intrare

5
2 4 -1 2 -1
4 -7 1 -6 -1
-9 2 4 5 -7
1 3 -2 6 2
1 -4 -6 -5 8

Ieșire

18

Explicație

Submatricea de sumă maximă este:
2 4 5
3 -2 6

#include <bits/stdc++.h>
using namespace std;

int n , a[301][301] , maxi , sp , b[301];

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
        {
            cin >> a[i][j];
            a[i][j] += a[i - 1][j];
        }
    maxi = -10000;
    for(int i = 1 ; i <= n ; i++)
        for(int j = i ; j <= n ; j++)
        {
            for(int k = 1 ; k <= n ; k++)
                b[k] = a[j][k] - a[i - 1][k];
            int sp = 0;
            for(int k = 1 ; k <= n ; k++)
            {
                sp += b[k];
                if(sp > maxi) maxi = sp;
                if(sp < 0) sp = 0;
            }
        }
    cout << maxi;
    return 0;
}