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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Maximum Sum Circular Subarray and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →