Maximum Frequency After Subarray Operation

lcpy gen -n 3434   # by problem number
lcpy gen -s maximum_frequency_after_subarray_operation   # by problem name

Input: nums = [1,2,3,4,5,6], k = 1
Output: 2

Input: nums = [10,2,3,4,5,5,4,3,2,2], k = 10
Output: 4

class Solution:
    # Time: O(50 * n) ~ O(n); Space: O(1)
    def max_frequency(self, nums: list[int], k: int) -> int:
        base = nums.count(k)
        best_gain = 0
        for target in sorted(set(nums) - {k}):
            # Kadane: +1 for target values (convertible to k), -1 for k values
            # (lost by the operation), 0 otherwise.
            cur = 0
            for num in nums:
                weight = 1 if num == target else (-1 if num == k else 0)
                cur = max(weight, cur + weight)
                best_gain = max(best_gain, cur)
        return base + best_gain