Competitive-Programming/Maximum_sum_submatrix.cpp at master · mnpal/Competitive-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int kadane(vector<int> A, int &cUp, int &cDown) {

    int current_sum = A[0];
    int max_sum = A[0];

    int a = 0;
    cUp = 0;
    cDown = 0;

    for(int i=1;i<A.size();i++) {
        current_sum = max(current_sum+A[i], A[i]);
        if(current_sum > max_sum) {
            a++;
            if(a==1)
                cUp = i;
            max_sum = current_sum;
            cDown = i;
        }

    }

    return max_sum;
}

void maxSubmatrixSum(vector<vector<int> > data) {

    int n = data.size();
    int m = data[0].size();

    int curr_sum = 0;
    int max_sum = 0;

    int maxLeft = 0;
    int maxRight = 0;
    int maxUp = 0;
    int maxDown = 0;

    for(int l=0;l<m;l++) {

        vector<int> sum(n, 0);
        for(int r=l;r<m;r++) {

            for(int j=0;j<n;j++) {
                sum[j] += data[j][r];
            }
            int cUp, cDown;
            curr_sum = kadane(sum, cUp, cDown);
            if(curr_sum > max_sum) {
                max_sum = curr_sum;
                maxRight = r;
                maxLeft = l;
                maxDown = cDown;
                maxUp = cUp;
            }

        }
    }

    cout << max_sum << "\t" << maxLeft << " " << maxRight << " " << maxUp << " " << maxDown << endl;

}

int main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<int> > data;

    for(int i=0;i<n;i++) {
        vector<int> row(m);
        for(int j=0;j<m;j++)
            cin >> row[j];
        data.push_back(row);
    }

    maxSubmatrixSum(data);

    return 0;
}