Maximum Score from K Multiplied Non-Overlapping Subarrays
You are given an integer array nums and a positive integer k.
You need to select exactly k non-overlapping, non-empty contiguous subarrays from nums such that their order from left to right is preserved.
The total score of the selection is calculated as the sum of each subarray's elements multiplied by its 1-based position index in the selection order. Specifically, if you select subarrays $S_1, S_2, \dots, S_k$ in order from left to right, the total score is:
$$\text{Score} = \sum_{i=1}^{k} (i \times \text{sum}(S_i))$$
Return the maximum total score possible.
[ "[1, -2, 3, 4, -1, 2]", "2" ]
Explanation. Selecting S1 = [1] (sum = 1) and S2 = [3, 4, -1, 2] (sum = 8) gives 1 * 1 + 2 * 8 = 17.
[ "[-5, 3, -1, 4]", "2" ]
Explanation. Selecting S1 = [3] (sum = 3) and S2 = [4] (sum = 4) gives 1 * 3 + 2 * 4 = 11.
[ "[-1, -2, -3]", "1" ]
Explanation. Selecting S1 = [-1] (sum = -1) gives 1 * -1 = -1, which is the maximum achievable.
[ "[5, 4, 3, 2, 1]", "3" ]
Explanation. Selecting S1 = [5] (sum = 5), S2 = [4] (sum = 4), and S3 = [3, 2, 1] (sum = 6) gives 1 * 5 + 2 * 4 + 3 * 6 = 31.
[ "[-2, 1, -3, 4, -1, 2, 1, -5, 4]", "3" ]
Explanation. Selecting S1 = [1] (sum = 1), S2 = [4, -1, 2, 1] (sum = 6), and S3 = [4] (sum = 4) gives 1 * 1 + 2 * 6 + 3 * 4 = 25.
Follow-up: Can you optimize the space complexity of your algorithm to O(k)?
`1 <= nums.length <= 1000` `-10^5 <= nums[i] <= 10^5` `1 <= k <= min(nums.length, 100)`