Leetcode problem 81 - Maximum Sum With Exactly K Elements

You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score:

Select an element m from nums. Remove the selected element m from the array. Add a new element with a value of m + 1 to the array. Increase your score by m. Return the maximum score you can achieve after performing the operation exactly k times.

Example 1:

Input: nums = [1,2,3,4,5], k = 3 Output: 18 Explanation: We need to choose exactly 3 elements from nums to maximize the sum. For the first iteration, we choose 5. Then sum is 5 and nums = [1,2,3,4,6] For the second iteration, we choose 6. Then sum is 5 + 6 and nums = [1,2,3,4,7] For the third iteration, we choose 7. Then sum is 5 + 6 + 7 = 18 and nums = [1,2,3,4,8] So, we will return 18. It can be proven, that 18 is the maximum answer that we can achieve. Example 2:

Input: nums = [5,5,5], k = 2 Output: 11 Explanation: We need to choose exactly 2 elements from nums to maximize the sum. For the first iteration, we choose 5. Then sum is 5 and nums = [5,5,6] For the second iteration, we choose 6. Then sum is 5 + 6 = 11 and nums = [5,5,7] So, we will return 11. It can be proven, that 11 is the maximum answer that we can achieve.

Constraints:

1 <= nums.length <= 100 1 <= nums[i] <= 100 1 <= k <= 100

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximizeSum = function (nums, k) {
  // Find the maximum value in the array 'nums'
  let max = Math.max(...nums);

  // Initialize a variable 'sum' to track the cumulative sum
  let sum = 0;

  // Iterate 'k' times to choose the maximum value and add it to the sum
  for (let i = 0; i < k; i++) {
    sum += max;
    // Increment the maximum value for the next iteration
    max += 1;
  }

  // Return the final sum
  return sum;
};

The time complexity of the function is O(n), where n is the length of the array ‘nums’. The function iterates through the array once to find the maximum value, and the subsequent loop runs ‘k’ times, resulting in a linear time complexity.

The space usage is constant, and the space complexity of the code is O(1). The space required does not grow with the size of the input array (nums) or the number of iterations (k).