LeetCode 2530: Maximal Score After Applying K Operations

Explanation

To solve this problem, we can use a greedy approach. We need to find the maximum score we can achieve by applying exactly k operations. We can achieve this by iteratively selecting the maximum element in the array, increasing our score by that element, and updating the array by dividing that element by 3 (and taking the ceiling value).

Here are the steps for the algorithm:

1. Initialize a variable score to 0 to keep track of the total score.
2. Perform the following steps k times:
   • Find the index maxIndex of the maximum element in the array nums.
   • Increase the score by nums[maxIndex].
   • Update nums[maxIndex] by taking the ceiling value of nums[maxIndex] / 3.
3. Return the final score.

The time complexity of this algorithm is O(kn) where n is the length of the input array nums. The space complexity is O(n) to store the input array.

class Solution {
    public int maximalScore(int[] nums, int k) {
        int score = 0;
        for (int i = 0; i < k; i++) {
            int maxIndex = 0;
            for (int j = 1; j < nums.length; j++) {
                if (nums[j] > nums[maxIndex]) {
                    maxIndex = j;
                }
            }
            score += nums[maxIndex];
            nums[maxIndex] = (int) Math.ceil(nums[maxIndex] / 3.0);
        }
        return score;
    }
}