Solution: Maximal Score After Applying K Operations

Statement

You are given a 0-indexed array of integer nums and an integer k. Your task is to maximize a score through a series of operations. Initially, your score is set to $0$.

In each operation:

1. Select an index i (where $0 ≤$ i $<$nums.length).

2. Add the value of nums[i] to your score.

3. Replace nums[i] with ceil(nums[i] / 3).

Repeat this process exactly k times and return the highest score you can achieve.

The ceiling function ceil(value) is the least integer greater than or equal to value.

Constraints:

• $1 \leq$ nums.length, k $\leq 10^3$

• $1 \leq$ nums[i] $\leq 10^5$

Solution

This algorithm maximizes the score by iteratively selecting and reducing the largest elements from the array. It uses a max heap to ensure efficient access to the largest element. Over k iterations, the algorithm repeatedly extracts the largest value, adds it to the total score, reduces it by dividing it by $3$ and rounding it up, and reinserts the reduced value into the heap.

The steps of the algorithm are as follows:

1. Create a maxHeap to store all elements of nums.

2. Initialize a variable score to 0 to keep track of the accumulated score.

3. Iterate for k steps, and in each iteration, perform the following steps:

   1. Pop the largest value from the heap using maxHeap.top and store this value in a variable largest.

   2. Add this value to the score.

   3. Calculate the reduced value of the extracted element as (largest + 2) / 3.

   4. Push the reduced value back into the heap using maxHeap.push to maintain the max heap.

4. After k iterations, return the accumulated score.

Let’s look at the following illustration to get a better understanding of the solution: