918. Maximum Sum Circular Subarray

How to solve Maximum Sum Circular Subarray (LeetCode 918): the approach in brief

The problem

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

Pattern

Maximum Sum Circular Subarray is a Dynamic Programming (DP) Patterns problem, in the 1D Array (Kadane's Algorithm for Max/Min Subarray) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Master Kadane's algorithm for finding maximum (or minimum) subarray sum in O(n) time.

Approach outline

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.

Complexity

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

Asked at

Maximum Sum Circular Subarray has been reported in interviews at Amazon, Bloomberg, Facebook, Google, Microsoft, Two Sigma, Uber.