[Note #3][Algorithm] Kadane’s algorithm

Maximum subarray sum

Given an array of n numbers, our task is to calculate the maximum subarray sum, i.e., the largest possible sum of a sequence of consecutive values in the array.

1. Brute force: O(n^3) or O(n^2).

2. Divide and Conquer: O(n log(n)).

3. Kadane’s algorithm (Dynamic Programming): O(n)

int best = 0, sum = 0;
for (int k = 0; k < n; k++) {
    sum = max(array[k], sum + array[k]);
    best = max(best, sum);
}
cout << best << "\n";