### aritra_roy's blog

By aritra_roy, history, 12 days ago, , 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. Comments (2)
 » 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.
•  » » 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?