What is the brute force approach and complexity for Maximum Sum Circular Subarray?

Walk every block on the circle, using % n to wrap; keep the largest sum with time complexity O(N^2) and space complexity O(1).

What is the optimal approach and complexity for Maximum Sum Circular Subarray?

Run Kadane for the largest and the smallest block sum; answer = max(largest, total − smallest) with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Maximum Sum Circular Subarray?

Look for key signals in the prompt: "circular array" indicates The array is a circle, so a block can wrap from the end back to the start.; "non-empty block" indicates The answer is a contiguous block on the circle. A wrapping block is the complement of one middle block.; "largest sum" indicates Maximising the wrap means minimising the middle, so the same Kadane runs for the smallest sum too..

Maximum Sum Circular Subarray

Medium·LeetCode #918Basic Anchor

LeetCode

Jump:

30-Second Mental ModelKadane twice (largest and smallest block) plus the total (Circular)

Complexity:O(N^2)→O(N)

Key Insight

A wrapping block is the whole circle minus one middle block, so its sum is total − (sum of the middle). To make the wrap as large as possible, make the middle block as small as possible. Run Kadane twice in one pass: once for the largest block and once for the smallest. The answer is the bigger of largest and total − smallest.

Core Validity Invariant

A wrapping block is total minus one non-empty middle block, so the best wrap is total minus the smallest middle block. The one exception is when every number is negative.

Problem

You are given an integer array nums that is circular: the element after the last one is the first one. A block of numbers can wrap around, going from the end of the array back to the start.

Return the largest sum of a non-empty block. A block may not use the same number twice.

Input

An integer array nums of length n, read as a circle.

Output

A single integer: the largest sum of any non-empty block on the circle.

Example 1

Input: nums = [1, -2, 3, -2]

Output: 3

The best block is [3] by itself. Wrapping does not help: [3, -2, 1] gives 2 and [1] gives 1.

Example 2

Input: nums = [5, -3, 5]

Output: 10

The block wraps around. The last 5 and the first 5 sit next to each other, so [5, 5] gives 10. Keeping the -3 in between would only give 7.

Example 3

Input: nums = [-3, -2, -3]

Output: -2

Every number is negative, so the best block is the least negative single number, -2.

Constraints

• n == nums.length
• 1 ≤ n ≤ 3 × 10^4
• −3 × 10^4 ≤ nums[i] ≤ 3 × 10^4

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
For a normal array, Kadane finds the best block. What new kind of block appears when the array is a circle?
2.
A block that wraps uses the end and the start of the array. Which part of the array does it leave out?
3.
If a wrapping block skips a middle part, how is its sum related to the total sum of the array?
4.
What happens to my answer if every single number is negative?
5.
How many blocks can a circle of n numbers have, and can I check them all fast enough?

Brute force approach

Idea

A block on the circle is decided by its start and its length, and the length is at most n. For each start, add the numbers one at a time, wrapping the index with % n, and keep the largest sum seen.

Thinking process

1
A block cannot use a number twice, so its length goes from 1 to n.
2
The index after the last one is 0 again. So read the numbers with (start + len − 1) % n.
3
Check on [5, -3, 5]. Start 0 gives 5, then 2, then 7. Start 1 gives -3, then 2. Start 2 gives 5, then 5 + 5 = 10 (the next index after 2 is 0), then 10 − 3 = 7.
4
The largest over all starts and lengths is 10.

Visual

Each step is one block on the circle. Orange cells wrap past the last index back to the first. There are n × n blocks, so the work grows with n².

Brute force tries every start and lengthnums = [5, -4, 6, -3, -2, 5] (circular)step 1/36

nums

-4

-3

-2

▲s

Work

start: 0
length: 1
sum: 5
best: 5

Block from 0, length 1

Start 0, length 1: the block sums to 5.

Code & Implementation

brute.cpp

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        long long best = LLONG_MIN;

        // A block is decided by its start and its length (1 to n, never more than n).
        for (int start = 0; start < n; start++) {
            long long sum = 0;
            for (int len = 1; len <= n; len++) {
                // (start + len - 1) % n wraps past the last index back to index 0.
                sum += nums[(start + len - 1) % n];
                best = max(best, sum);
            }
        }
        return (int)best;
    }
};

Complexity

Time O(N^2)Space O(1)

There are n starts and up to n lengths for each one, so about n² sums. With n = 3 × 10^4 that is about 9 × 10^8 additions, which is too slow.

Better approach

Why brute force is slow

Each start walks up to n numbers and adds them again from scratch.

What repeated work are we doing?

A block's sum is a difference of prefix sums. Blocks from neighbouring starts share almost all their numbers, but the brute force adds those shared numbers again for every start.

What information can we reuse?

Prefix sums turn any plain block into one subtraction. The best-prefix and best-suffix values turn each wrapping block into one addition per split point.

New approach

Idea

A block that does not wrap is a difference of two prefix sums. A block that wraps is a suffix plus a prefix, with a gap in between. Store the best prefix sum up to each index and the best suffix sum from each index. Then each split point gives its best wrap with one lookup.

Thinking process

1
Prefix sums: pre[i] = nums[0] + … + nums[i]. A plain block [l … r] sums to pre[r] − pre[l − 1].
2
A wrapping block contains the last number and the first number. So it is a suffix (ending at n − 1) plus a prefix (starting at 0), and the two must not overlap.
3
So for each split point i, the best wrap is (best prefix ending at or before i) + (best suffix starting after i).
4
Check on [5, -3, 5]. The prefix sums are 5, 2, 7. The best prefix ending at or before index 0 is 5. The best suffix starting after index 0 is max(-3 + 5, 5) = 5. So the wrap is 5 + 5 = 10.

Code & Implementation

better.cpp

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();

        // pre[i] = nums[0] + ... + nums[i]
        vector<long long> pre(n);
        pre[0] = nums[0];
        for (int i = 1; i < n; i++) pre[i] = pre[i - 1] + nums[i];

        // sufMax[k] = largest sum of a block that starts at index k or later and ends at n - 1.
        vector<long long> sufMax(n + 1, LLONG_MIN);
        long long suffix = 0;
        for (int k = n - 1; k >= 0; k--) {
            suffix += nums[k];
            sufMax[k] = max(sufMax[k + 1], suffix);
        }

        long long best = LLONG_MIN;

        // Not wrapping: block [l .. r] sums to pre[r] - pre[l - 1].
        // Keep the smallest earlier prefix; pre[-1] = 0 stands for the empty prefix.
        long long minBefore = 0;
        for (int r = 0; r < n; r++) {
            best = max(best, pre[r] - minBefore);
            minBefore = min(minBefore, pre[r]);
        }

        // Wrapping: a prefix that ends at or before i, plus a suffix that starts after i.
        long long preMax = LLONG_MIN;
        for (int i = 0; i + 1 < n; i++) {
            preMax = max(preMax, pre[i]);
            best = max(best, preMax + sufMax[i + 1]);
        }
        return (int)best;
    }
};

Complexity

Time O(N)Space O(N)

Two passes build the prefix sums and the best suffix sums, both stored in arrays of length n. The optimal below reaches the same answer with O(1) extra space.

Optimized approach

Idea

Start from brute force

Brute force tries every start and every length, which is about n² sums.

Find the repeated work

A wrapping block covers the circle minus one plain middle block. So instead of building the wrap from its numbers, we subtract a middle block from the total, and Kadane finds the smallest middle in one pass.

Define the state — what variables do I need?

total: Sum of all numbers. It never changes.
curMax, best: curMax is the largest block sum ending at the current index. best is the largest of these (the largest plain block so far).
curMin, worst: curMin is the smallest block sum ending at the current index. worst is the smallest of these (the smallest middle block so far).

Define validity

A wrapping block is total minus one non-empty middle block, so the best wrap is total minus the smallest middle block. The one exception is when every number is negative.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

total = 0; curMax = 0; curMin = 0; best = LLONG_MIN; worst = LLONG_MAX

The running sums start empty. The first number then sets them, because max(x, 0 + x) = x.

Every number x

total += x; curMax = max(x, curMax + x); best = max(best, curMax); curMin = min(x, curMin + x); worst = min(worst, curMin)

Kadane for the largest block ending here, and the same idea with min for the smallest. Starting fresh at x is the other option, so the running sum is never worse than the best of the two.

After the loop

if (best < 0) return best; else return max(best, total − worst)

A negative best means every number is negative, so there is no non-empty wrap. Otherwise the wrap total − worst is a real block (or harmlessly 0 when the middle is the whole array), so we compare it with the normal best.

What does the current window add to the answer?

After the loop, best is the largest block that does not wrap, and total − worst is the largest block that wraps. The larger of the two is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        long long total = 0;
        long long curMax = 0, curMin = 0;  // best block sums ending at the current index
        long long best = LLONG_MIN;        // largest block sum (normal Kadane)
        long long worst = LLONG_MAX;       // smallest block sum: the middle part we remove

        for (int x : nums) {
            total += x;
            curMax = max((long long)x, curMax + x);
            best = max(best, curMax);
            curMin = min((long long)x, curMin + x);
            worst = min(worst, curMin);
        }

        // All numbers negative: the smallest middle block is the whole array,
        // so total - worst would be the empty block (0). Return the largest single number.
        if (best < 0) return (int)best;
        return (int)max(best, total - worst);
    }
};

Complexity

Time O(N)Space O(1)

One pass with a few running values. The all-negative check is needed, as the mistakes below show.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Walk every block on the circle, using % n to wrap; keep the largest sum	O(N^2)	O(1)
Better	Prefix sums give any plain block; a wrap pairs the best prefix with the best suffix	O(N)	O(N)
Optimal	Run Kadane for the largest and the smallest block sum; answer = max(largest, total − smallest)	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“circular array”The array is a circle, so a block can wrap from the end back to the start.
“non-empty block”The answer is a contiguous block on the circle. A wrapping block is the complement of one middle block.
“largest sum”Maximising the wrap means minimising the middle, so the same Kadane runs for the smallest sum too.

Circular contiguous block+wrap = total − middle block+answer = max(Kadane max, total − Kadane min), unless all are negative→Kadane twice (largest and smallest block) plus the total (Circular)

This is Kadane applied to the complement. A plain maximum-subarray question stops at the array's ends, but a circular block can wrap, and a wrapping block is the total minus one middle block. So the same Kadane that finds the largest sum also finds the smallest middle block, and the answer uses both. The all-negative guard is the one extra rule that only the circle needs.

Don't make this mistake

Pattern confusion: forgetting the all-negative case

✗ return max(maxK, total - minK);

✓ if (maxK < 0) return maxK; return max(maxK, total - minK);

On [-3, -2, -3] the smallest middle block is the whole array, which sums to -8. So total - minK = -8 - (-8) = 0. That is the empty block, and the code returns 0 instead of -2. Every number is negative, so the best answer is the least negative number, -2.

Subtracting the largest block instead of the smallest

✗ return max(maxK, total - maxK);

✓ return max(maxK, total - minK);

On the dry run [5, -4, 6, -3, -2, 5] the total is 7 and the largest plain block is 7. So total - maxK = 0, which is not a real block. The real wrap is 7 - (-5) = 12, which removes the smallest middle block [-3, -2].

Reading past the end in the brute force

✗ sum += nums[start + len - 1];

✓ sum += nums[(start + len - 1) % n];

The brute force must wrap. On [5, -4, 6, -3, -2, 5], start 4 with length 3 reads index 6, which does not exist. The modulo sends it back to index 0, the 5 at the front of the array.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Kadane / Subarray translate into production architectures and low-level memory mechanics.

LLD Architecture