bihariforces's blog

Maximize Subarray Length to Mode Frequency Ratio
By bihariforces, history, 17 hours ago, In English

You are given an array $$$a$$$ of length $$$n$$$.

For any subarray, define its mode frequency as the maximum number of occurrences of any value within this subarray.

Find the maximum value of

$$$ \frac{\text{length of subarray}}{\text{mode frequency}} $$$

over all subarrays.

Constraints: $$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le a_i \le n$$$.

Print the maximum possible value of the expression. Your answer will be accepted if its absolute or relative error does not exceed $$$10^{-6}$$$.

Give this interesting problem a try!

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
16 hours ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

isnt the answer just always 1 like any subarray of length 1 gives that

→ Reply
  • »
    »
    16 hours ago, hide # ^ |
     
    Vote: I like it +2 Vote: I do not like it

    well 1 is the minimum

    the problem asked for the maximum possible value

    → Reply
    • »
      »
      »
      16 hours ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      but mode frequence is <= subarray length so length / mode frequency <= 1 so isnt 1 maximum

      → Reply
      • »
        »
        »
        »
        16 hours ago, hide # ^ |
         
        Vote: I like it +1 Vote: I do not like it

        oh ok sorry i understand

        → Reply
      • »
        »
        »
        »
        15 hours ago, hide # ^ |
         
        Vote: I like it +1 Vote: I do not like it

        mode <= length so length / mode is always >= 1 btw

        → Reply