You are given an integer array nums and two integers k and mul.
Select exactly k elements from nums. Process these elements one by one in any order you choose.
For each selected element, independently choose one of the following:
mul and add the result to the total sum.After processing each selected element, mul decreases by 1, regardless of which option was chosen. The current value of mul may become 0 or negative.
Return an integer denoting the maximum possible total sum.
Example 1:
Input: nums = [6,1,2,9], k = 3, mul = 2
Output: 26
Explanation:
One optimal way:
nums[3] = 9, nums[0] = 6, and nums[2] = 2.nums[3] = 9 first: choose multiplication, so it contributes 9 * 2 = 18. Now, mul becomes 1.nums[0] = 6 next: choose multiplication, so it contributes 6 * 1 = 6. Now, mul becomes 0.nums[2] = 2 last: choose addition, so it contributes 2.18 + 6 + 2 = 26.Example 2:
Input: nums = [3,7,5,2], k = 2, mul = 4
Output: 43
Explanation:
One optimal way:
nums[1] = 7 and nums[2] = 5.nums[1] = 7 first: choose multiplication, so it contributes 7 * 4 = 28. Now, mul becomes 3.nums[2] = 5 next: choose multiplication, so it contributes 5 * 3 = 15.28 + 15 = 43.Example 3:
Input: nums = [4,4], k = 1, mul = 1
Output: 4
Explanation:
One optimal way:
nums[0] = 4.nums[0] = 4: choose multiplication, so it contributes 4 * 1 = 4.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= k <= nums.length1 <= mul <= 105