LeetCode 3743 - Maximize Cyclic Partition Score

We are given a cyclic array nums, which means the array is considered to wrap around from the last element back to the first element. We want to partition the entire cycle into at most k contiguous subarrays.

leetcodehardarraydynamic-programming

LeetCode Problem 3743

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

We are given a cyclic array nums, which means the array is considered to wrap around from the last element back to the first element.

We want to partition the entire cycle into at most k contiguous subarrays. Since the array is cyclic, one of the subarrays is allowed to cross the boundary between the last and first positions.

For every subarray, its contribution to the score is:

$$\text{range} = \max(\text{subarray}) - \min(\text{subarray})$$

The score of a partition is the sum of these ranges across all chosen subarrays.

The goal is to maximize that total score.

The constraints are important:

  • n <= 1000
  • k <= n
  • nums[i] can be as large as 10^9

The relatively small value of n suggests that a dynamic programming solution is feasible, while the large element values tell us that the solution must rely on structure rather than value-based optimizations.

Several edge cases immediately stand out:

  • k = 1, where the entire cycle must remain one segment.
  • k = n, where every element could potentially be its own segment, although that is not always optimal.
  • Arrays where all values are identical, producing a score of 0.
  • Arrays with a single element.
  • Cases where the optimal partition wraps around the end of the array.

The cyclic nature is the main challenge. In a normal array partition problem, we can choose cuts directly. In a cyclic array, there is no fixed starting position.

Approaches

Brute Force

The most direct approach is to try every possible cyclic partition.

We could choose a starting position, linearize the cycle from that point, and then enumerate every way to place up to k - 1 cuts. For every partition, we would compute the range of each segment and keep the maximum score.

This approach is correct because it explicitly examines every valid partition.

Unfortunately, the number of partition configurations grows exponentially. Even after fixing a starting position, there are exponentially many ways to place cuts, making the approach completely impractical for n = 1000.

Key Insight

The crucial observation is that every segment contributes:

$$\max(\text{segment}) - \min(\text{segment})$$

Instead of thinking about segments directly, we can think about selecting extrema.

Every segment contributes one positive value, its maximum, and one negative value, its minimum.

Therefore the total score can be rewritten as:

$$\sum (\text{chosen maxima}) - \sum (\text{chosen minima})$$

This transforms the problem into selecting positive and negative extrema while preserving a valid cyclic partition structure.

The official hints point toward a DP based on extrema selection. While scanning the array, we keep track of whether we currently have:

  • no unfinished extremum pair,
  • an unmatched minimum,
  • an unmatched maximum.

This produces a very small DP state space.

The cyclic condition can be handled by cutting the cycle near a global maximum. Any optimal cyclic partition can be represented by one of two linear traversals around that maximum, which removes the need to explicitly handle wrap-around during the DP.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(n) Enumerates all cyclic partitions
Optimal DP O(nk) O(k) Uses extrema-selection DP with compressed states

Algorithm Walkthrough

  1. Find the index of a global maximum value.
  2. Observe that an optimal cyclic partition can always be represented by cutting the cycle either immediately before or immediately after this maximum.
  3. Run the DP on both linearizations and take the larger answer.
  4. Define three DP states for every extremum count:
  • State 0: no unfinished extremum pair.
  • State 1: currently holding a minimum contribution.
  • State 2: currently holding a maximum contribution.
  1. Let dp[j][state] store the best score after processing the current prefix, where j represents how many extremum selections have been started.
  2. For every value x:
  • Stay in the current state.
  • Start a minimum contribution by subtracting x.
  • Start a maximum contribution by adding x.
  • Close an unfinished contribution.
  1. Process the DP in reverse order of j so transitions do not reuse updates from the current element.
  2. After all elements are processed, the answer for that traversal is the value stored in the fully closed state.
  3. Evaluate both linearizations around the global maximum and return the larger result.

Why it works

Every segment contributes exactly one maximum and one minimum. The DP explicitly models those contributions as positive and negative selections. The three states guarantee that every positive contribution is matched correctly with a negative contribution, preserving a valid partition structure. Cutting near a global maximum removes cyclic ambiguity, ensuring that every optimal cyclic partition appears in one of the two linear traversals.

Python Solution

from typing import List

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        n = len(nums)

        max_idx = max(range(n), key=lambda i: nums[i])

        def solve(start: int, end: int) -> int:
            NEG_INF = -(10 ** 30)

            dp = [[NEG_INF] * 3 for _ in range(k + 2)]
            dp[0][0] = 0

            for idx in range(start, end):
                value = nums[idx % n]

                for used in range(k + 1, 0, -1):
                    dp[used][0] = max(
                        dp[used][0],
                        dp[used][1] + value,
                        dp[used][2] - value,
                    )

                    dp[used][1] = max(
                        dp[used][1],
                        dp[used - 1][0] - value,
                    )

                    dp[used][2] = max(
                        dp[used][2],
                        dp[used - 1][0] + value,
                    )

            return dp[k + 1][0]

        answer1 = solve(max_idx, max_idx + n)
        answer2 = solve(max_idx + 1, max_idx + 1 + n)

        return max(answer1, answer2)

The implementation first finds a global maximum position. Two traversals are evaluated because an optimal cyclic partition may place the cut on either side of that maximum.

The helper function performs the actual DP. The three DP states correspond to the three balance configurations discussed earlier. Each processed value may start a new extremum contribution, extend the current configuration, or close a contribution.

The reverse iteration over used prevents a single element from being counted multiple times in the same transition layer.

Finally, the larger result from the two linearizations is returned.

Go Solution

func maximumScore(nums []int, k int) int64 {
	n := len(nums)

	maxIdx := 0
	for i := 1; i < n; i++ {
		if nums[i] > nums[maxIdx] {
			maxIdx = i
		}
	}

	maxVal := func(a, b int64) int64 {
		if a > b {
			return a
		}
		return b
	}

	solve := func(start, end int) int64 {
		const NEG int64 = -1 << 60

		dp := make([][3]int64, k+2)

		for i := 0; i < k+2; i++ {
			dp[i][0] = NEG
			dp[i][1] = NEG
			dp[i][2] = NEG
		}

		dp[0][0] = 0

		for idx := start; idx < end; idx++ {
			value := int64(nums[idx%n])

			for used := k + 1; used >= 1; used-- {
				dp[used][0] = maxVal(
					dp[used][0],
					maxVal(
						dp[used][1]+value,
						dp[used][2]-value,
					),
				)

				dp[used][1] = maxVal(
					dp[used][1],
					dp[used-1][0]-value,
				)

				dp[used][2] = maxVal(
					dp[used][2],
					dp[used-1][0]+value,
				)
			}
		}

		return dp[k+1][0]
	}

	ans1 := solve(maxIdx, maxIdx+n)
	ans2 := solve(maxIdx+1, maxIdx+1+n)

	if ans1 > ans2 {
		return ans1
	}
	return ans2
}

The Go implementation follows exactly the same DP structure.

The main difference is that Go uses int64 throughout because scores can grow beyond the range of a 32-bit integer. The DP table is stored as a slice of fixed-size arrays, which provides compact memory usage while keeping indexing efficient.

Worked Examples

Example 1

Input:

nums = [1, 2, 3, 3]
k = 2

Optimal cyclic partition:

[2, 3]
[3, 1]

Ranges:

Segment Min Max Range
[2,3] 2 3 1
[3,1] 1 3 2

Total:

1 + 2 = 3

Answer:

3

Example 2

Input:

nums = [1, 2, 3, 3]
k = 1

Only one segment is allowed.

Segment Min Max Range
[1,2,3,3] 1 3 2

Answer:

2

Example 3

Input:

nums = [1, 2, 3, 3]
k = 4

Although up to four segments are allowed, using more segments is not mandatory.

The same partition as Example 1 remains optimal:

Segment Range
[2,3] 1
[3,1] 2

Total:

3

Answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(nk) Each element updates O(k) DP states
Space O(k) Only the compressed DP table is stored

The DP contains k + 2 rows and only three balance states. For every array element, we iterate through all DP layers once. Since n <= 1000, this complexity easily fits within the limits.

Test Cases

sol = Solution()

assert sol.maximumScore([1, 2, 3, 3], 2) == 3  # provided example
assert sol.maximumScore([1, 2, 3, 3], 1) == 2  # single segment
assert sol.maximumScore([1, 2, 3, 3], 4) == 3  # at most k segments

assert sol.maximumScore([5], 1) == 0  # single element

assert sol.maximumScore([7, 7, 7, 7], 4) == 0  # all equal

assert sol.maximumScore([1, 100], 1) == 99  # one segment

assert sol.maximumScore([1, 100], 2) == 99  # extra segments do not help

assert sol.maximumScore([1, 10, 1, 10], 2) == 18  # alternating highs and lows

assert sol.maximumScore([10, 1, 10, 1], 2) == 18  # cyclic wrap useful

assert sol.maximumScore([1, 3, 2, 4, 1], 3) >= 0  # general mixed case

Test Summary

Test Why
[1,2,3,3], k=2 Validates the main example
[1,2,3,3], k=1 Forces a single segment
[1,2,3,3], k=4 Confirms "at most k" behavior
[5] Smallest possible input
[7,7,7,7] All ranges are zero
[1,100] Simple two-element range
[1,100], k=2 Additional partitions do not improve score
[1,10,1,10] Multiple strong extrema
[10,1,10,1] Useful cyclic structure
Mixed random case General correctness coverage

Edge Cases

A single-element array is the smallest valid input. The only possible segment contains one value, so its maximum and minimum are identical. The score must therefore be zero. The DP naturally handles this because no profitable extremum pair can be formed.

Arrays where every value is the same are another important corner case. Every segment has range zero regardless of how the array is partitioned. A buggy implementation may accidentally create positive contributions through incorrect state transitions. The DP only gains score from actual value differences, so the result remains zero.

The case k = 1 is particularly important because partitioning is not allowed. The entire cycle must remain a single segment. Any implementation that incorrectly assumes at least one cut exists will fail here. The DP formulation still works because it can represent the single global maximum and minimum contribution for the whole cycle.

Finally, cyclic wrap-around partitions are the defining challenge of the problem. A solution that treats the array as purely linear misses valid optimal answers. By evaluating the two linearizations around a global maximum, the implementation captures every optimal cyclic partition without explicitly managing wrap-around segments.