-
Notifications
You must be signed in to change notification settings - Fork 0
/
maxSumSubRectangle.CPP
108 lines (81 loc) · 2.64 KB
/
maxSumSubRectangle.CPP
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// Example program
#include <iostream>
#include <string>
#include <vector>
#define unsigned int uint
using namespace std;
class KadaneResult{
int _maxSum;
int _start;
int _end;
public:
KadaneResult(int maxSum, int start, int end):_maxSum(maxSum), _start(start),_end(end){}
KadaneResult kadaneAlgo(vector<int> A){
int max = 0;
int maxStart=-1;
int maxEnd = -1;
int currentStart = 0;
int maxSoFar = 0;
for(int i=0; i<arr.length; ++i){
maxSoFar += arr[i];
if(maxSoFar < 0){
maxSoFar = 0;
currentStart = i+1;
}
if(max < maxSoFar){
maxStart = currentStart;
maxEnd = i;
max = maxSoFar;
}
}
return KadaneResult(max,maxStart,maxEnd);
}
};
class Result{
int _maxSum;
int _L,_R,_U,_D;
public:
string to_string(){
return "Result: [ maxSum = "+to_string(_maxSum) + " L="+to_string(_L) + " R="+
to_string(_R) + " U=" + to_string(_U) + " D="+to_string(D);
}
Result maxSum(vector< vector<int> > &M){
int rows = M.size();
int cols = M[0].size();
vector<int> A(rows,0);
Result result = new Result();
for(int left = 0; left < cols; ++left){
for(int i=0; i<rows; ++i)
A[i] = 0;
for(int right = left; right < cols; ++right){
for(int i=0; i<rows; ++i){
A[i] += M[i][right];
}
KadaneResult kadaneResult = kadaneAlgo(A);
if(kadaneResult.maxSum > result.maxSum){
result.maxSum = kadaneResult.maxSum;
result.L = left;
result.R= right;
result.U = kadaneResult.start;
result.D=kadaneResult.end;
}
}
}
return result;
}
};
void printT(vector< vector<int> > &T){
for(uint i=0; i< T.size(); ++i){
for(uint j=0; j<T[0].size(); ++j){
cout << T[i][j] << " ";
}
cout<< endl;
}
}
int main()
{
vector< vector<int>> M = { {2,1,-3,-4,5}, {0,6,3,4,1}, {2,-2,-1,4,-5},{-3,3,1,0,3}};
printT(M);
cout << maxSumSubrectangle(M) << endl;
return 0;
}