918. Maximum Sum Circular Subarray

Maximum Sum Circular Subarray (LeetCode 918) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern.

• NeetCode 250 · #209 of 250 · Greedy

How to solve Maximum Sum Circular Subarray

Maximum Sum Circular Subarray is a Kadane's Algorithm problem, part of Dynamic Programming (DP) Patterns. Master Kadane's algorithm for finding maximum (or minimum) subarray sum in O(n) time.

Work towards the solution in these steps:

1. Consider how you might use dynamic programming to find maximum sums within subarrays of a linear array as a starting point.
2. Recall Kadane's algorithm, which efficiently finds the maximum subarray sum in a non-circular array in O(n) time.
3. Think about how the circular nature of the array could be handled by considering subarrays that wrap around the end to the beginning of the array.

The reference solution runs in O(n) time and O(1) space.

The Maximum Sum Circular Subarray solution and editorial walks through the full approach with reference code.

Problem statement

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 = 0.) Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1: Input: [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3

Example 2: Input: [5,-3,5] Output: 10 Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3: Input: [3,-1,2,-1] Output: 4 Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4: Input: [3,-2,2,-3] Output: 3 Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5: Input: [-2,-3,-1] Output: -1 Explanation: Subarray [-1] has maximum sum -1 Note: -30000 <= A[i] <= 30000 1 <= A.length <= 30000

Topics and companies

Topics: Array.

Reported in interviews at Amazon, Bloomberg, Facebook, Google, Microsoft, Two Sigma, Uber.

How to practise Maximum Sum Circular Subarray on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Maximum Sum Circular Subarray in the code editor, or read the Maximum Sum Circular Subarray editorial for a worked solution with its approach and complexity analysis.

Where Maximum Sum Circular Subarray sits in the DSA pattern sheet

• Dynamic Programming (DP) Patterns pattern guide
• 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern
• The full DSA patterns sheet

Problems related to Maximum Sum Circular Subarray

Other problems that use the same 1D Array (Kadane's Algorithm for Max/Min Subarray) and Dynamic Programming (DP) Patterns techniques:

• Maximum Absolute Sum of Any Subarray — Medium, same subpattern
• Maximum Product Subarray — Medium, same subpattern
• Maximum Subarray — Medium, same subpattern
• Best Time to Buy and Sell Stock — Easy, same pattern
• Best Time to Buy and Sell Stock II — Medium, same pattern
• Best Time to Buy and Sell Stock III — Hard, same pattern

Maximum Sum Circular Subarray FAQ