-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMaximum_Subarray.cpp
More file actions
76 lines (57 loc) · 1.76 KB
/
Copy pathMaximum_Subarray.cpp
File metadata and controls
76 lines (57 loc) · 1.76 KB
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
class Solution {
public:
int maxSubArray(int A[], int n) {
int sum = 0;
int max_sum = A[0]; // contain at least one element
for(int i = 0; i < n ; i++){
sum += A[i];
// make sure every elememt is compared
if(sum > max_sum){
max_sum = sum;
}
if(sum < 0){
sum = 0;
}
}
return max_sum;
}
};
/* Divide and conquer solution */
class Solution {
public:
int maxSubArray(int A[], int n) {
int max_sum;
max_sum = max_sub_helper(A, 0, n);
return max_sum;
}
private:
int max_sub_helper(int A[], int sInd, int eInd){
if (sInd+1 == eInd) return A[sInd]; // one elem array
if (sInd >= eInd) return INT_MIN; // empty array
int l_max, r_max, c_max;
int mInd;
mInd = sInd + (eInd-sInd)/2;
l_max = max_sub_helper(A, sInd, mInd);
r_max = max_sub_helper(A, mInd+1, eInd);
c_max = A[mInd];
int prefix_sum = 0;
int prefix_max = INT_MIN;
for (int i = mInd+1; i < eInd; i++) {
prefix_sum += A[i];
if (prefix_sum > prefix_max) prefix_max = prefix_sum;
}
if (prefix_max > 0) {
c_max += prefix_max;
}
int suffix_sum = 0;
int suffix_max = INT_MIN;
for (int i = mInd-1; i >= 0; i--) {
suffix_sum += A[i];
if (suffix_sum > suffix_max) suffix_max = suffix_sum;
}
if (suffix_max > 0) {
c_max += suffix_max;
}
return max(max(l_max, r_max), c_max);
}
};