-
Notifications
You must be signed in to change notification settings - Fork 2
/
max_subarray.cpp
34 lines (29 loc) · 912 Bytes
/
max_subarray.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
/*
Max Subarray
#array
Have the function MaxSubarray(arr) take the array of numbers stored in arr and determine
the largest sum that can be formed by any contiguous subarray in the array. For example,
if arr is [-2, 5, -1, 7, -3] then your program should return 11 because the sum is
formed by the subarray [5, -1, 7]. Adding any element before or after this subarray
would make the sum smaller.
Optimal: o(n), achieved: o(n)
*/
#include <iostream>
#include <string>
#include <algorithm>
int MaxSubarray(int arr[], int arrLength) {
// code goes here
int cs{}, bs{INT32_MIN};
for (size_t i{}; i < arrLength; i++) {
cs = std::max(arr[i],cs + arr[i]);
bs = std::max(cs, bs);
}
return bs;
}
int main(void) {
// keep this function call here
int A[] = coderbyteInternalStdinFunction(stdin);
int arrLength = sizeof(A) / sizeof(*A);
std::cout << MaxSubarray(A, arrLength);
return 0;
}