Skip to content

3434. Maximum Frequency After Subarray Operation

Description

You are given an array nums of length n. You are also given an integer k.

You perform the following operation on nums once:

  • Select a subarray nums[i..j] where 0 <= i <= j <= n - 1.
  • Select an integer x and add x to all the elements in nums[i..j].

Find the maximum frequency of the value k after the operation.

 

Example 1:

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

Output: 2

Explanation:

After adding -5 to nums[2..5], 1 has a frequency of 2 in [1, 2, -2, -1, 0, 1].

Example 2:

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

Output: 4

Explanation:

After adding 8 to nums[1..9], 10 has a frequency of 4 in [10, 10, 11, 12, 13, 13, 12, 11, 10, 10].

 

Constraints:

  • 1 <= n == nums.length <= 105
  • 1 <= nums[i] <= 50
  • 1 <= k <= 50

Solutions

Solution 1

Thinking

One operation rewrites a subarray to \(k\); we want the maximum frequency of \(k\) afterwards. \(n\le 10^5\) but values are at most \(50\).

The new frequency is the original count of \(k\) plus how many non-\(k\) cells in the subarray become \(k\). That is a Kadane problem on a \(+1/-1\) encoding.

For each original value \(x\neq k\), run maximum subarray on \(+1\) for \(x\) and \(-1\) for \(k\), then add the global count of \(k\). The tiny alphabet makes \(O(50n)\) acceptable.

1


1


1


1

Comments