forked from Firkraag/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmaximum-subarray-inline.c
More file actions
65 lines (59 loc) · 1.65 KB
/
maximum-subarray-inline.c
File metadata and controls
65 lines (59 loc) · 1.65 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
#include <stdio.h>
#include <limits.h>
struct value {
int low;
int high;
int sum;
};
//An inline solution to find maximum subarray
//FIND_MAXIMUM_SUBARRAY(A, low, high)
// sum = A[low]
// left = low
// right = high
// max-endpoint-sum = NEGATIVE INFINITE
// for i = low to high
// if max-endpoint-sum >= 0
// max-endpoint-sum = max-endpoint-sum + A[i]
// max-endpoint-high = i
// else
// max-endpoint-sum = A[i]
// max-endpoint-low = max-endpoint-high = i
// if max-endpoint-sum > sum
// sum = max-endpoint-sum
// left = max-endpoint-low
// right = max-endpoint-high
// return(left, right, sum)
struct value FIND_MAXIMUM_SUBARRAY(int A[], int low, int high) {
struct value max_endpoint, max;
int i;
max.sum = A[low];
max.low = low;
max.high = high;
max_endpoint.sum = INT_MIN;
for (i = low; i <= high; i++) {
if (max_endpoint.sum >= 0) {
max_endpoint.sum = max_endpoint.sum + A[i];
max_endpoint.high = i;
}
else {
max_endpoint.sum = A[i];
max_endpoint.low = max_endpoint.high = i;
}
if (max_endpoint.sum > max.sum) {
max.sum = max_endpoint.sum;
max.low = max_endpoint.low;
max.high = max_endpoint.high;
}
}
return max;
}
int main() {
int a[17] = { 13, -3, -25, -20, -3, -16, 23, 18, 20, -7, 12, -5, 22, -15, -4, 7, 0};
int b[9] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
struct value max;
max = FIND_MAXIMUM_SUBARRAY(a, 0, 16);
printf("%d, %d, %d, %d, %d\n", max.low, max.high, max.sum, a[max.low], a[max.high]);
max = FIND_MAXIMUM_SUBARRAY(b, 0, 8);
printf("%d, %d, %d, %d, %d\n", max.low, max.high, max.sum, b[max.low], b[max.high]);
return 0;
}