Maximum Frequency After Subarray Operation

• Calculate initial_k_count, the total number of k's in the original nums array.
• Initialize max_gain = 0. This will store the maximum possible net increase in the frequency of k.
• Iterate through all possible start indices i from 0 to n-1.
• For each i, iterate through all possible end indices j from i to n-1. This defines the subarray nums[i..j].
• For each subarray, create a frequency map to count the occurrences of each number within nums[i..j].
• From the frequency map, determine k_in_subarray, the count of k.
• Also, find max_v_in_subarray, which is the highest frequency of any number v (where v != k) in the subarray.
• The gain for this specific subarray and the best choice of v is max_v_in_subarray - k_in_subarray.
• Update the global max_gain with this gain if it's larger.
• After checking all subarrays, the final result is initial_k_count + max_gain.

The fundamental idea is to simulate the process for every single choice we can make. A choice consists of a subarray nums[i..j] and a value x to add. The optimal x for a given subarray is one that converts an existing number v into k, i.e., x = k - v. This operation converts all occurrences of v in the subarray to k but also changes any original k's within the subarray. The net change in the frequency of k is count(v, nums[i..j]) - count(k, nums[i..j]). To find the best outcome for a subarray nums[i..j], we must find the value v that maximizes this gain. The brute-force algorithm iterates through all O(n^2) subarrays, and for each, it takes O(n) time to build a frequency map and find the best v, leading to an overall cubic time complexity.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maxFrequency(int[] nums, int k) {6        int n = nums.length;7        int initialKCount = 0;8        for (int num : nums) {9            if (num == k) {10                initialKCount++;11            }12        }13 14        int maxGain = 0;15        for (int i = 0; i < n; i++) {16            for (int j = i; j < n; j++) {17                // Subarray nums[i..j]18                Map<Integer, Integer> freqMap = new HashMap<>();19                for (int l = i; l <= j; l++) {20                    freqMap.put(nums[l], freqMap.getOrDefault(nums[l], 0) + 1);21                }22 23                int kInSubarray = freqMap.getOrDefault(k, 0);24                int maxVInSubarray = 0;25                for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {26                    if (entry.getKey() != k) {27                        maxVInSubarray = Math.max(maxVInSubarray, entry.getValue());28                    }29                }30                31                int gain = maxVInSubarray - kInSubarray;32                maxGain = Math.max(maxGain, gain);33            }34        }35 36        return initialKCount + maxGain;37    }38}

• Calculate initial_k_count.
• Initialize max_gain = 0.
• Iterate through all possible start indices i from 0 to n-1.
• For each i, initialize an empty frequency map.
• Start a second loop for the end index j from i to n-1.
• In the j loop, update the frequency map by adding nums[j]. This incrementally builds the map for the subarray nums[i..j].
• With the updated map, find k_in_subarray and max_v_in_subarray (the max frequency of any element v != k).
• Calculate the gain and update the global max_gain.
• The final result is initial_k_count + max_gain.

The core logic of maximizing the gain count(v, nums[i..j]) - count(k, nums[i..j]) remains the same. The improvement lies in the computation. We fix the left boundary i of the subarray and iterate the right boundary j from i to n-1. As we expand the subarray, we don't need to re-scan it. We can maintain a frequency map for nums[i..j] and just add nums[j] to it at each step. After updating the map, we find the best v to convert by scanning the map's values. Since the range of values is small (1-50), scanning the map or a fixed range of potential values takes O(C) time. This optimization reduces the complexity from cubic to quadratic.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maxFrequency(int[] nums, int k) {6        int n = nums.length;7        int initialKCount = 0;8        for (int num : nums) {9            if (num == k) {10                initialKCount++;11            }12        }13 14        int maxGain = 0;15        for (int i = 0; i < n; i++) {16            Map<Integer, Integer> freqMap = new HashMap<>();17            for (int j = i; j < n; j++) {18                // Update frequency map for subarray nums[i..j]19                freqMap.put(nums[j], freqMap.getOrDefault(nums[j], 0) + 1);20 21                int kInSubarray = freqMap.getOrDefault(k, 0);22                int maxVInSubarray = 0;23                // Since values are 1-50, we can iterate 1-50 instead of map keys24                for (int val = 1; val <= 50; val++) {25                    if (val != k) {26                        maxVInSubarray = Math.max(maxVInSubarray, freqMap.getOrDefault(val, 0));27                    }28                }29                30                int gain = maxVInSubarray - kInSubarray;31                maxGain = Math.max(maxGain, gain);32            }33        }34 35        return initialKCount + maxGain;36    }37}

• First, calculate initial_k_count, the frequency of k in the entire array.
• Initialize max_gain = 0.
• Iterate through each possible value v from 1 to 50. This v is the candidate number we will transform into k.
• If v == k, skip it, as this operation results in no change (gain is 0).
• For each v, we want to find the subarray that maximizes count(v, subarray) - count(k, subarray). This is a maximum subarray sum problem.
• We can solve this using Kadane's algorithm. Iterate through nums, maintaining a current_gain.
• For each element nums[i]: if it's v, add 1 to current_gain; if it's k, subtract 1. Otherwise, add 0.
• If current_gain becomes negative, reset it to 0 (as we can always start a new subarray).
• Keep track of the maximum current_gain seen for this v (max_gain_for_v).
• After iterating through nums, update the overall max_gain = max(max_gain, max_gain_for_v).
• The final answer is initial_k_count + max_gain.

The key insight is that the final frequency of k is initial_k_count + gain, where gain = count(v, nums[i..j]) - count(k, nums[i..j]). We need to maximize this gain over all choices of i, j, v.

We can iterate through all possible values for v (from 1 to 50, as per constraints) and for each v, find the maximum possible gain. For a fixed v, the problem is to find max_{i,j} (count(v, nums[i..j]) - count(k, nums[i..j])).

This is equivalent to finding the maximum subarray sum on a transformed array where nums[p] == v maps to +1, nums[p] == k maps to -1, and all other numbers map to 0. The sum of a subarray in this transformed array represents the gain. Kadane's algorithm finds the maximum subarray sum in linear time.

By applying Kadane's algorithm for each potential value v, we can find the overall maximum gain efficiently.

1class Solution {2    public int maxFrequency(int[] nums, int k) {3        int n = nums.length;4        int initialKCount = 0;5        for (int num : nums) {6            if (num == k) {7                initialKCount++;8            }9        }10 11        int maxGain = 0;12        // Iterate through all possible values 'v' to be converted to 'k'13        for (int v = 1; v <= 50; v++) {14            if (v == k) {15                continue;16            }17 18            // Use Kadane's algorithm to find the max gain for this 'v'19            int currentGain = 0;20            int maxGainForV = 0;21            for (int num : nums) {22                int score = 0;23                if (num == v) {24                    score = 1; // We gain an element that becomes k25                } else if (num == k) {26                    score = -1; // We lose an original k27                }28                29                currentGain += score;30                31                if (currentGain < 0) {32                    currentGain = 0; // Start a new potential subarray33                }34                maxGainForV = Math.max(maxGainForV, currentGain);35            }36            maxGain = Math.max(maxGain, maxGainForV);37        }38 39        return initialKCount + maxGain;40    }41}