Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Maximum Circular Subarray Sum

Medium · Arrays · Asked at Amazon, Microsoft, Adobe, Goldman Sachs

The array is circular (the last element is followed by the first). Print the maximum sum of a non-empty subarray, where a subarray may wrap around the end but may use each element at most once.

Input

First line: n. Second line: n space-separated integers.

Output

The maximum circular subarray sum.

Constraints

Answer = max(normal Kadane, total − minimum subarray). If every number is negative, the second option is empty — use Kadane's result.

Example 1

Input

3
5 -3 5

Output

10

Example 2

Input

3
-3 -2 -3

Output

-2

Hints

  1. A non-wrapping answer is ordinary Kadane's.
  2. A wrapping subarray leaves out a contiguous middle part — so its sum is total − (minimum subarray sum).

Approach

Run Kadane twice in one pass: maxSub (best normal subarray) and minSub (smallest subarray). The best wrapping subarray is total − minSub. Answer = max(maxSub, total − minSub) — except when all numbers are negative: then minSub = total, the "wrapping" option would be the empty subarray, so answer maxSub.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long total = 0, curMax = 0, curMin = 0, maxSub = LLONG_MIN, minSub = LLONG_MAX, x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        total += x;
        curMax = max(x, curMax + x);
        maxSub = max(maxSub, curMax);
        curMin = min(x, curMin + x);
        minSub = min(minSub, curMin);
    }
    cout << (maxSub < 0 ? maxSub : max(maxSub, total - minSub)) << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
a = data[1:]
total = cur_max = cur_min = 0
max_sub, min_sub = float("-inf"), float("inf")
for x in a:
    total += x
    cur_max = max(x, cur_max + x)
    max_sub = max(max_sub, cur_max)
    cur_min = min(x, cur_min + x)
    min_sub = min(min_sub, cur_min)
print(max_sub if max_sub < 0 else max(max_sub, total - min_sub))

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long total = 0, curMax = 0, curMin = 0, maxSub = Long.MIN_VALUE, minSub = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            total += x;
            curMax = Math.max(x, curMax + x);
            maxSub = Math.max(maxSub, curMax);
            curMin = Math.min(x, curMin + x);
            minSub = Math.min(minSub, curMin);
        }
        System.out.println(maxSub < 0 ? maxSub : Math.max(maxSub, total - minSub));
    }
}

Solve Maximum Circular Subarray Sum online · All practice problems