TomoLink
CompaniesZeptoData Structures & AlgorithmsMaximum Sum Circular Subarray
DSA
MediumArray

Maximum Sum Circular Subarray

arraydivide and conquerdynamic programming

Problem Statement

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 .

Examples

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

Constraints

n == nums.length
1 <= n <= 3 * 10 ^4
-3 * 10 ^4 <= nums[i] <= 3 * 10 ^4
🤔
Medium
Difficulty
Topic Info
ModuleDSA
CategoryArray
Sub-topicDivide and Conquer
Tags
arraydivide and conquerdynamic programmingqueuemonotonic queue
Navigation
Maximum Sum Circular Subarray [Medium] | Zepto Dsa | TomoLink