Print the largest sum of a run of one or more neighbouring numbers. For 2 -4 3 -1 2 -6 4 1 it is 5 (4 + 1). Solve it with divide and conquer: the best run lies in the left half, in the right half, or across the middle.
What to build
A divide-and-conquer program that finds the largest sum of neighbouring numbers.
Requirements
- Return the number itself for a range of one number.
- Compute the best run in each half, and the best run across the middle.
- Print the largest of the three.
Input
A line with n (1 ≤ n ≤ 1000), then n whole numbers from −10 000 to 10 000.
Output
The largest sum. The run must contain at least one number, so when all numbers are negative the answer is the largest of them.
Constraints
1 ≤ n ≤ 1000, and each number is from −10 000 to 10 000.
Example
Input:
8
2 -4 3 -1 2 -6 4 1
Output:
5
Why it works
A run is either completely in one half or crosses the middle, so the three cases cover every possible run. The cost follows T(n) = 2T(n/2) + O(n), which is O(n log n).
Examples
8 2 -4 3 -1 2 -6 4 1
5
3 -3 -1 -2
-1
Hints
Hint 1
Write best(lo, hi). With one number, the answer is that number.
Hint 2
Otherwise split at mid. The answer is the largest of: best(lo, mid), best(mid + 1, hi), and the best run crossing the middle.
Hint 3
The crossing run: the largest sum ending at mid (walk left from mid) plus the largest sum starting at mid + 1 (walk right).
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int a[1000];
int crossing(int lo, int mid, int hi) {
int sum = 0, left = a[mid];
for (int i = mid; i >= lo; i--) {
sum += a[i];
if (sum > left) left = sum;
}
sum = 0;
int right = a[mid + 1];
for (int i = mid + 1; i <= hi; i++) {
sum += a[i];
if (sum > right) right = sum;
}
return left + right;
}
int best(int lo, int hi) {
if (lo == hi) return a[lo];
int mid = (lo + hi) / 2;
int l = best(lo, mid), r = best(mid + 1, hi), c = crossing(lo, mid, hi);
int m = l > r ? l : r;
return m > c ? m : c;
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
printf("%d\n", best(0, n - 1));
return 0;
}