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";
