Skip to main content

918. Maximum Sum Circular Subarray

medium

Maximum subarray sum on a circular array. Reduce to two Kadane runs: best linear, plus total minus worst linear for wraparound.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums. A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n]. A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.

Constraints

  • n == nums.length
  • 1 <= n <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4

Examples

Example 1

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

Explanation: Subarray [3] has maximum sum 3.

Example 2

Input
nums = [5,-3,5]
Output
10

Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.

Example 3

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

Explanation: Subarray [-2] has maximum sum -2.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Either the answer is a regular Kadane subarray, or it wraps around the end and begins again.

Hint 2

A wrapping subarray's sum equals total - (some non-empty inner subarray). Minimize that inner subarray to maximize the wrap.

Hint 3

Return max(kadane_max, total - kadane_min). Handle the all-negative edge case by returning kadane_max.

Solution approach

Reveal approach

Two parallel Kadane sweeps. Compute kadane_max (the standard maximum-subarray sum) and kadane_min (the minimum-subarray sum — same algorithm with min replacing max). Let total = sum(nums). The optimal answer is either a contiguous subarray (kadane_max) or a wrapping subarray that excludes a non-empty middle slice (total - kadane_min). Return max(kadane_max, total - kadane_min). Edge case: if every element is negative, kadane_min equals total, and total - kadane_min = 0 corresponds to picking an empty subarray — not allowed. Detect this by checking kadane_max < 0 and returning kadane_max directly. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • kadane

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

More DP 1D practice problems

See all DP 1D problems →