Description
You are given an integer array nums of length n and an integer k.
You need to choose exactly k non-empty subarrays nums[l..r] of nums. Subarrays may overlap, and the exact same subarray (same l and r) can be chosen more than once.
The value of a subarray nums[l..r] is defined as: max(nums[l..r]) - min(nums[l..r]).
The total value is the sum of the values of all chosen subarrays.
Return the maximum possible total value you can achieve.
Example 1:
Input: nums = [1,3,2], k = 2
Output: 4
Explanation:
One optimal approach is:
- Choose
nums[0..1] = [1, 3]. The maximum is 3 and the minimum is 1, giving a value of3 - 1 = 2. - Choose
nums[0..2] = [1, 3, 2]. The maximum is still 3 and the minimum is still 1, so the value is also3 - 1 = 2.
Adding these gives 2 + 2 = 4.
Example 2:
Input: nums = [4,2,5,1], k = 3
Output: 12
Explanation:
One optimal approach is:
- Choose
nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of5 - 1 = 4. - Choose
nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also4. - Choose
nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again4.
Adding these gives 4 + 4 + 4 = 12.
Constraints:
1 <= n == nums.length <= 5 * 1040 <= nums[i] <= 1091 <= k <= 105
Solutions
This JavaScript function, maxTotalValue, finds the overall range of a list of numbers and multiplies it by a given number k. It works by first scanning through the input array nums to find both the smallest (minimum) and largest (maximum) values. To do this, it starts by assuming the first number in the list is both the minimum and maximum, and then loops through the rest of the numbers, updating these values whenever it encounters a smaller or larger number. Finally, the function subtracts the minimum value from the maximum value to get their difference, multiplies that difference by k, and returns the final result.
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxTotalValue = function(nums, k) {
const n = nums.length;
let min = nums[0];
let max = nums[0];
for (let i = 1; i < n; i++) {
if (nums[i] < min) {
min = nums[i];
} else if (nums[i] > max) {
max = nums[i];
}
}
return (max - min) * k;
};