The 30 second answer
I use Kadane's algorithm: one pass that keeps the best sum ending here and the best sum so far, in linear time and constant space. At each number I either extend the previous run or start a new one here, then update the global best. Both values start at the first element, so an all-negative array returns the largest element. Follow-ups are the indices, divide and conquer, and the circular variant.
The usual statement is LeetCode's Maximum Subarray problem: given an integer array nums, return the largest sum of any non-empty contiguous subarray. Official examples: [-2,1,-3,4,-1,2,1,-5,4] returns 6, from the subarray [4,-1,2,1]; [1] returns 1; [5,4,-1,7,8] returns 23.
Kadane's algorithm. At each index i, the best non-empty sum that ends here is max(nums[i], bestEndingAtPrevious + nums[i]): either start a new run at i, or extend the previous run. The answer is the largest of those ending sums. Wikipedia describes this scan and states that it runs in O(n) time and O(1) extra space. Some textbook formulations allow an empty subarray, whose sum is 0; that version would return 0 on an all-negative array. LeetCode does not allow an empty subarray, so both running values must start at nums[0], not at 0. Then an all-negative array correctly returns its largest element: [-3,-2,-5] returns -2.
public class MaximumSubarray {
// Kadane: O(n) time, O(1) extra space. The subarray must be non-empty.
static int maxSubArray(int[] nums) {
int best = nums[0], cur = nums[0];
for (int i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}
// Follow-up: also return [bestSum, leftInclusive, rightInclusive].
static int[] maxSubArrayRange(int[] nums) {
int best = nums[0], cur = nums[0];
int bestL = 0, bestR = 0, curL = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > cur + nums[i]) {
cur = nums[i];
curL = i;
} else {
cur += nums[i];
}
if (cur > best) {
best = cur;
bestL = curL;
bestR = i;
}
}
return new int[] {best, bestL, bestR};
}
// Official follow-up: divide and conquer, O(n log n).
static int maxSubArrayDC(int[] nums) {
return maxSubArrayDC(nums, 0, nums.length - 1);
}
static int maxSubArrayDC(int[] nums, int lo, int hi) {
if (lo == hi) return nums[lo];
int mid = (lo + hi) >>> 1;
int leftBest = maxSubArrayDC(nums, lo, mid);
int rightBest = maxSubArrayDC(nums, mid + 1, hi);
int crossLeft = nums[mid], sum = 0;
for (int i = mid; i >= lo; i--) {
sum += nums[i];
crossLeft = Math.max(crossLeft, sum);
}
int crossRight = nums[mid + 1];
sum = 0;
for (int i = mid + 1; i <= hi; i++) {
sum += nums[i];
crossRight = Math.max(crossRight, sum);
}
return Math.max(Math.max(leftBest, rightBest), crossLeft + crossRight);
}
// Circular variant (LeetCode 918). If every value is negative, do not
// take the empty wrap-around (total minus the whole array).
static int maxSubarraySumCircular(int[] nums) {
int maxBest = nums[0], maxCur = nums[0];
int minBest = nums[0], minCur = nums[0];
int total = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
total += x;
maxCur = Math.max(x, maxCur + x);
maxBest = Math.max(maxBest, maxCur);
minCur = Math.min(x, minCur + x);
minBest = Math.min(minBest, minCur);
}
if (maxBest < 0) return maxBest;
return Math.max(maxBest, total - minBest);
}
public static void main(String[] args) {
int[] ex1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(maxSubArray(ex1)); // 6
System.out.println(java.util.Arrays.toString(
maxSubArrayRange(ex1))); // [6, 3, 6] -> [4, -1, 2, 1]
System.out.println(maxSubArrayDC(ex1)); // 6
System.out.println(maxSubArray(new int[] {-3, -2, -5})); // -2
System.out.println(maxSubarraySumCircular(new int[] {1, -2, 3, -2})); // 3
System.out.println(maxSubarraySumCircular(new int[] {5, -3, 5})); // 10
System.out.println(maxSubarraySumCircular(new int[] {-3, -2, -3})); // -2
}
}Follow-up: return the indices. Keep the start of the current run. When you start a new run, set that start to i. When the global best improves, record the current start and i. On the official first example this yields indices 3 through 6, the subarray [4,-1,2,1].
Follow-up: divide and conquer. This is the official LeetCode follow-up after the linear solution. Wikipedia also records an O(n log n) divide-and-conquer algorithm found before Kadane's linear scan. Split the array at mid. The best subarray is entirely in the left half, entirely in the right half, or it crosses mid, in which case it is the best suffix of the left half plus the best prefix of the right half, found with two linear walks from mid. The recurrence is T(n) = 2T(n/2) + O(n), which is O(n log n).
Follow-up: circular array. LeetCode's Maximum Sum Circular Subarray asks for the same maximum when the array wraps, still without reusing an element. A wrapping candidate equals the total sum minus the minimum subarray, which is the middle segment you drop. Return the larger of ordinary Kadane and that wrapping sum, except when every element is negative: then total minus the minimum subarray is 0, the empty wrap, which is invalid, so return the ordinary Kadane value (the largest element). Official examples: [1,-2,3,-2] returns 3; [5,-3,5] returns 10 from the two wrapping fives; [-3,-2,-3] returns -2.
Sources (3)
- LeetCode 53: Maximum Subarrayleetcode.com
- Wikipedia: Maximum subarray problemen.wikipedia.org
- LeetCode 918: Maximum Sum Circular Subarrayleetcode.com