aritra_roy's blog

By aritra_roy, history, 7 months ago, In English,

I couldn't understand as to what this problem is trying to specify. Link. At first I thought it was like the Longest Increasing Subsequence problem with an addition that the frequency of B[i] > B[j] is also a condition that should immediately follow. But seems like that's not the case. Looking at the editorial also didn't help. Can somebody pls help me understand the problem.

  • Vote: I like it
  • 0
  • Vote: I do not like it

7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

The problem boils down to something like this-

For any two different value elements in the sub sequence picked from A, the higher value element should have higher frequency.

So if you picked elements with values 1 2(For the sample), then the frequency of number of elements of value 1(freq=1) should be less than that of value 2(Freq=2). Ans = freq(1)+freq(2)=3.


  • »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay, so reading through your solution I get what you are trying to do. You are trying every possible frequency for a particular A[i] and then checking which one fits the best. The recurrence relation is:

    If f(pos, i) represent the max subsequence that can be formed by A[pos..n-1] (assuming 0 based indexing) taking the frequency of the previously added character i, then f(pos, i) = max{f(pos+1, i), f(pos+1, k) + i} for i+1 <= k <= freq[a[pos]]

    The answer is f(0, 0).

    Am I correct?