Loading…
Loading…
The largest sum of any contiguous subarray, in one pass: whenever the running sum goes negative, throw it away and start again.
Start with the first element alone: current sum -2, best so far -2. Nothing has been compared yet — Kadane never looks back more than one step.
1int maxSubarray(int[] a) {2 int best = a[0], cur = a[0];3 for (int i = 1; i < a.length; i++) {4 if (cur < 0) cur = 0; // a negative prefix can never help — drop it5 cur += a[i];6 best = Math.max(best, cur);7 }8 return best;9}