Maximize Capped Contribution Sum
You are given two integer arrays a and b of the same length and an integer k. For each index i, that index contributes min(a[i], b[i]) to a total sum.
You may choose at most k distinct indices. For each chosen index, replace b[i] with 2 * b[i]. After applying those changes, the contribution of that index becomes min(a[i], 2 * b[i]).
Return the maximum possible total contribution.
Complete the function maximizeCappedContributionSum in the editor below.
maximizeCappedContributionSum has the following parameters:
int[] a: the first arrayint[] b: the second arrayint k: the maximum number of indices whoseb[i]value can be doubled
Returns
long: the maximum possible total sum.
a = [5, 8, 4] b = [3, 6, 10] k = 1 return = 15
The initial contribution is min(5,3) + min(8,6) + min(4,10) = 3 + 6 + 4 = 13. If you double b[0], the first contribution becomes min(5,6) = 5. If you double b[1], the second becomes min(8,12) = 8. Either choice gives a gain of 2, so the best total is 15.
a = [10, 7, 6, 4] b = [2, 5, 4, 3] k = 2 return = 18
The initial total is 2 + 5 + 4 + 3 = 14. Doubling index 0 changes its contribution to min(10,4)=4, a gain of 2. Doubling index 1 changes its contribution to min(7,10)=7, a gain of 2. Doubling index 2 changes its contribution to min(6,8)=6, a gain of 2. Any two of those three gains produce the maximum total 14 + 2 + 2 = 18.
The source thread did not provide explicit numeric bounds.
a.length == b.length0 <= k <= a.length- Each index may be doubled at most once.
public long maximizeCappedContributionSum(int[] a, int[] b, int k) {
// write your code here
}