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.
你給予一個整數陣列 nums（長度為 n）和一個整數 k。 你需要選擇恰好 k 個非空子陣列，子陣列可以重疊，也可以重複選擇同一個子陣列。 每個子陣列的定義為：max(nums[l..r]) - min(nums[l..r]) total value 是所有選中子陣列的值總和。 回傳能夠得到的最大 total value。
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 of 3 - 1 = 2. Choose nums[0..2] = [1, 3, 2]. The maximum is still 3 and the minimum is still 1, so the value is also 3 - 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 of 5 - 1 = 4. Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also 4. Choose nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again 4. Adding these gives 4 + 4 + 4 = 12.
solution:
因為我們不知道陣列中的最大、最小值為何，但是我們可以假設 index = 0 為初始值。
接著從題目給的敘述，我們發現可以重複選擇同一組子陣列，
所以我們可以直接使用數學方法找出最大值與最小值的差，
最後就可以將總和乘上題目給的 k 次，即為最大總和。
Code 1: BigO(n)
function maxTotalValue(nums: number[], k: number): number {
let [maxNum] = nums, [minNum] = nums, result: number = 0
for (const num of nums) {
maxNum = Math.max(maxNum, num);
minNum = Math.min(minNum, num);
result = Math.max(result, (maxNum - minNum))
}
return result * k;
};
FlowChart:
Example 1
Input: nums = [1,3,2], k = 2 maxNum = nums[0] = 1 minNum = nums[0] = 1 maxNum = Math.max(1, 1) -> 1 minNum = Math.min(1, 1) -> 1 result = Math.max(0, (1 - 1)) = 0 maxNum = Math.max(1, 3) -> 3 minNum = Math.min(1, 3) -> 1 result = Math.max(0, (3 - 1)) = 2 maxNum = Math.max(3, 2) -> 3 minNum = Math.min(1, 2) -> 1 result = Math.max(0, (3 - 1)) = 2 return result * k -> 2 * 2 = 4
Example 2
Input: nums = [4,2,5,1], k = 3 maxNum = nums[0] = 4 minNum = nums[0] = 4 maxNum = Math.max(4, 4) -> 4 minNum = Math.min(4, 4) -> 4 result = Math.max(0, (4 - 4)) = 0 maxNum = Math.max(4, 2) -> 4 minNum = Math.min(4, 2) -> 2 result = Math.max(0, (4 - 2)) = 2 maxNum = Math.max(4, 5) -> 5 minNum = Math.min(2, 5) -> 2 result = Math.max(0, (5 - 2)) = 3 maxNum = Math.max(5, 1) -> 5 minNum = Math.min(2, 1) -> 1 result = Math.max(0, (5 - 1)) = 4 return result * k -> 4 * 3 = 12