All problems

Maximum Sum Circular Subarray

Medium · dynamic programming

A round conveyor belt carries parcels, and nums[i] is the value of the parcel at position i. Some values are negative (damaged parcels cost money). The belt is a loop: the last position is followed by the first.

Pick a non-empty stretch of neighbouring positions along the loop. The stretch may run past the end of the list and carry on from the start, but it may not use any position twice. Return the largest total value such a stretch can have.

Examples

Example 1

Input: nums = [1, -2, 3, -2]

Output: 3

The single parcel 3 is the best stretch.

Example 2

Input: nums = [5, -3, 5]

Output: 10

Start at the last 5 and wrap round to the first 5. The stretch [5, 5] skips the -3.

Example 3

Input: nums = [-3, -2, -4]

Output: -2

Every parcel is negative and the stretch cannot be empty, so take the single best parcel.

Constraints