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:
k = 2 subarrays. One optimal partition is [5] and [1, 2, 1].sumArr = 5 and value = 5 × 6 / 2 = 15.sumArr = 1 + 2 + 1 = 4 and value = 4 × 5 / 2 = 10.15 + 10 = 25, which is the minimum possible score.Example 2:
Input: nums = [1,2,3,4], k = 1
Output: 55
Explanation:
k = 1 subarray, all elements belong to the same subarray: [1, 2, 3, 4].sumArr = 1 + 2 + 3 + 4 = 10 and value = 10 × 11 / 2 = 55.Example 3:
Input: nums = [1,1,1], k = 3
Output: 3
Explanation:
k = 3 subarrays. The only valid partition is [1], [1], [1].sumArr = 1 and value = 1 × 2 / 2 = 1.1 + 1 + 1 = 3, which is the minimum possible score.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1041 <= k <= nums.length Solutions for this problem are being prepared.
Try solving it yourselfPractice Minimum Partition Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor