Skip to content

3826. Minimum Partition Score

SourceBiweekly Contest 175 Q4DifficultyHardRating2345

Description

You are given an integer array nums and an integer k.

Your task is to partition nums into exactly k subarrays and return an integer denoting the minimum possible score among all valid partitions.

The score of a partition is the sum of the values of all its subarrays.

The value of a subarray is defined as sumArr * (sumArr + 1) / 2, where sumArr is the sum of its elements.

 

Example 1:

Input: nums = [5,1,2,1], k = 2

Output: 25

Explanation:

  • We must partition the array into k = 2 subarrays. One optimal partition is [5] and [1, 2, 1].
  • The first subarray has sumArr = 5 and value = 5 × 6 / 2 = 15.
  • The second subarray has sumArr = 1 + 2 + 1 = 4 and value = 4 × 5 / 2 = 10.
  • The score of this partition is 15 + 10 = 25, which is the minimum possible score.

Example 2:

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

Output: 55

Explanation:

  • Since we must partition the array into k = 1 subarray, all elements belong to the same subarray: [1, 2, 3, 4].
  • This subarray has sumArr = 1 + 2 + 3 + 4 = 10 and value = 10 × 11 / 2 = 55.​​​​​​​
  • The score of this partition is 55, which is the minimum possible score.

Example 3:

Input: nums = [1,1,1], k = 3

Output: 3

Explanation:

  • We must partition the array into k = 3 subarrays. The only valid partition is [1], [1], [1].
  • Each subarray has sumArr = 1 and value = 1 × 2 / 2 = 1.
  • The score of this partition is 1 + 1 + 1 = 3, which is the minimum possible score.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 104
  • 1 <= k <= nums.length

Solutions

Solution 1

Thinking

Split the array into exactly \(k\) pieces, each scoring \(\textit{sum}(\textit{sum}+1)/2\), and minimize the total. \(n \le 1000\) makes \(O(n^2 k)\) borderline; constants matter.

The partition has optimal substructure: the best \(t\)-piece split of a prefix depends only on \((t-1)\)-piece splits of shorter prefixes.

The piece cost is convex in the prefix sum, so adjacent decisions are monotone and a deque can reduce each layer from quadratic to linear.

We therefore DP by number of pieces, evaluate a piece from prefix sums, and maintain the decision queue implied by convexity.

1


1


1


1

Comments