918. Circular Subarray Sum

Quick Review

Max Subarray Sum 👈 This is a classic bottom up DP problem. It can be solved with Kadane's algorithm in $O(n)$ time and $O(1)$ space.

GeeksforGeeks explanation of Kadane's algorithm

☝️ If you aren't yet familiar with Kadane's algorithm, read this article first.

Once you've got problem 53, come tackle this trickier problem 918.

Circular Subarray Sum

Problem 53 only allows us to find two indices $i$ and $j$ in an array $nums$ of length $n$,

satisfying $0 \leq i \leq j < n$, to maximize $\text{sum}(nums[i: j + 1])$.

Problem 918 accepts the same type of subarray as problem 53,

but it also accepts circular subarrays: find two indices $i$ and $j$ satisfying $0 \leq i \leq j < n$,

maximizing $\text{sum}(nums[:i] + nums[j:])$

In short, this means taking a prefix and a suffix from $nums$, with the constraint that no indices can be used twice.

The Naive Wrong Path 🫨

To be honest, when I first solved problem 53,

I tried the "array concatenation" approach —

concatenating $nums$ into $nums + nums$ and applying problem 53's logic directly.

That ended with five wrong answers over two and a half months 🤣

Time for Reverse Thinking 😌

Almost three months later, one day outside my home, there was construction going on 🚧 with an excavator digging into the ground 🪏

Watching the excavator scoop downward, I suddenly realized that:

problem 918 requires "excavation"!

That is, find the subarray with the most negative sum in $nums$,

subtract it from $\text{sum}(nums)$, and apply "addition by subtraction" to eliminate this deficit — what remains is the maximum circular subarray sum 😁

Kadane's algorithm in problem 53 finds the maximum subarray,

and here we need to find the subarray with the minimum negative sum,

so we just negate it: a reversal of thinking.

The Excavator Can't Dig Recklessly

Just as construction must avoid hitting water pipes or power lines,

we must make sure we don't "dig out everything".

What do I mean? Consider the case where all elements in $nums$ are non-positive.

The most negative subarray would simply be $\text{sum}(nums)$,

and subtracting it from $\text{sum}(nums)$ leaves an empty subarray —

an empty subarray is not allowed.

How shall we fix things? Simply track $max(nums)$:

I. If $max(nums) \leq 0$, every element has no positive contribution.

In this case, pick the element with the least poison — that's $max(nums)$.

II. When $max(nums) > 0$, the answer is one of:

1. A standard maximum subarray as in problem 53.
2. A circular subarray: $\text{sum}(nums)$ minus the most negative subarray.

Take the larger of these two.

So we have some key variables to track:

1. maxPosSum: maximum positive subarray sum
2. minNegSum: minimum negative subarray sum
3. arrayTotalSum: $\text{sum}(nums)$
4. maxNum: $max(nums)$

The overall logic still follows problem 53's spirit.

C++

#include <vector>
using namespace std;

int computeMaxCircularSubarraySum(vector<int>& nums) {
    int arrayTotalSum = 0;
    int maxNum = nums.front();

    int posSubarraySum = 0, maxPosSum = 0;

    int negSubarraySum = 0, minNegSum = 0;

    for (const auto& num : nums) {
        if (num > maxNum)
            maxNum = num;

        arrayTotalSum += num;

        posSubarraySum += num;
        if (posSubarraySum > maxPosSum)
            maxPosSum = posSubarraySum;

        if (posSubarraySum <= 0) // Positive sum <= 0: reset subarray.
            posSubarraySum = 0;

        negSubarraySum += num;
        if (negSubarraySum < minNegSum)
            minNegSum = negSubarraySum;

        if (negSubarraySum >= 0) // Negative sum >= 0: reset subarray.
            negSubarraySum = 0;
    }

    if (maxPosSum == 0) // All numbers are non-positive.
        return maxNum;

    return max(arrayTotalSum - minNegSum, maxPosSum);
}

Python

def compute_max_circular_subarray_sum(nums: list[int]) -> int:
    array_total_sum = 0
    max_num = nums[0]

    pos_subarray_sum, max_pos_sum = 0, 0

    neg_subarray_sum, min_neg_sum = 0, 0

    for num in nums:
        if num > max_num:
            max_num = num

        array_total_sum += num

        pos_subarray_sum += num
        if pos_subarray_sum > max_pos_sum:
            max_pos_sum = pos_subarray_sum

        if pos_subarray_sum <= 0:  # Positive sum <= 0: reset subarray.
            pos_subarray_sum = 0

        neg_subarray_sum += num
        if neg_subarray_sum < min_neg_sum:
            min_neg_sum = neg_subarray_sum

        if neg_subarray_sum >= 0:  # Negative sum >= 0: reset subarray.
            neg_subarray_sum = 0

    if max_num <= 0:
        return max_num  # All numbers are non-positive.

    return max(array_total_sum - min_neg_sum, max_pos_sum)

A fresh perspective lets us solve this quirky problem in $O(n)$ time and $O(1)$ space.

Though sometimes it takes a long while before the right perspective finally arrives 😹