Scale Engineer

Maximum Sum Circular Subarray

Med
#0872Time: O(n^2), where n is the length of the input array. The two nested loops result in a quadratic number of operations as we check every start position against every possible length.Space: O(1), as we only use a constant amount of extra space for variables like `maxGlobalSum` and `currentSum`.2 companies
Patterns
Dynamic Programming
Algorithms
Divide and Conquer
Data structures
ArrayQueueMonotonic Queue
Companies
FlipkartTwo Sigma

Prompt

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.

 

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.

 

Constraints:

  • n == nums.length
  • 1 <= n <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104

Approaches

2 approaches with complexity analysis and trade-offs.

This approach exhaustively checks every possible contiguous subarray in the circular array. It iterates through all possible starting points and, for each starting point, considers all possible lengths from 1 up to the total number of elements n. By calculating the sum for each of these subarrays and keeping track of the maximum sum found, it guarantees finding the correct answer.

Algorithm

  • Initialize max_global_sum with a very small number (or the first element).
  • Use a nested loop structure. The outer loop i from 0 to n-1 selects the starting element of the subarray.
  • The inner loop j from 0 to n-1 determines the length of the subarray (from 1 to n).
  • Inside the inner loop, calculate the sum of the current subarray. To handle wrapping, use the modulo operator: index = (i + j) % n.
  • Keep a current_sum for the subarray starting at i and extending for j+1 elements.
  • After calculating the sum of each possible subarray, compare it with max_global_sum and update if it's larger.
  • After all loops complete, max_global_sum will hold the result.

Walkthrough

The brute-force method systematically explores all potential subarrays. A subarray in a circular context is defined by its starting position and its length. We can implement this with two nested loops.

  • The outer loop iterates through each element of the array, nums[i], treating it as the starting point of a potential maximum subarray.
  • The inner loop then extends the subarray from this starting point, one element at a time. It calculates the sum of the current subarray and updates the overall maximum sum found so far.
  • The circular nature of the array is handled by using the modulo operator (%) to calculate the indices of elements, which allows the subarray to 'wrap around' from the end of the array to the beginning.
class Solution {    public int maxSubarraySumCircular(int[] nums) {        int n = nums.length;        int maxGlobalSum = Integer.MIN_VALUE;         for (int i = 0; i < n; i++) {            int currentSum = 0;            for (int j = 0; j < n; j++) {                int index = (i + j) % n;                currentSum += nums[index];                if (currentSum > maxGlobalSum) {                    maxGlobalSum = currentSum;                }            }        }        return maxGlobalSum;    }}

Complexity

Time

O(n^2), where n is the length of the input array. The two nested loops result in a quadratic number of operations as we check every start position against every possible length.

Space

O(1), as we only use a constant amount of extra space for variables like `maxGlobalSum` and `currentSum`.

Trade-offs

Pros

  • Simple to understand and implement.

  • It is a straightforward translation of the problem definition into code.

Cons

  • Highly inefficient for larger arrays due to its quadratic time complexity.

  • Likely to result in a 'Time Limit Exceeded' error on competitive programming platforms for typical constraints.

Solutions

class Solution {public  int maxSubarraySumCircular(int[] nums) {    int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0];    for (int i = 1; i < nums.length; ++i) {      total += nums[i];      f1 = nums[i] + Math.max(f1, 0);      f2 = nums[i] + Math.min(f2, 0);      s1 = Math.max(s1, f1);      s2 = Math.min(s2, f2);    }    return s1 > 0 ? Math.max(s1, total - s2) : s1;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem