All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Sartaj's partner, Katekar is very loyal to his job and also to Sartaj. In his dedication towards his duty, he often neglects his wife who ends up alone and sad. Today, katekar has promised his wife to reach home early and spend time with her. However he and Sartaj are stuck with a problem which may decide the future of Mumbai. As Katekar cannot leave in such a situation, help him to solve the problem so that he can get back to his wife. 

You are given an array \(A\) of length \(N \). You need to detemine the largest subsequence \(B\) from the given array \(A\) such that for any index \(i\) and \(j\) in \(B\) if \(B[i] > B[j]\) then the frequency of \(B[i]\) is strictly greater than the frequency of \(B[j]\).

Input format :

• First line : a single integer \(N\) denoting the length of given array.
• Second line : \(N\) space seperated integers denoting the array elements.

Output fromat :

• Print the length of largest subsequence \(B\) that can be formed.

Constraints :

• \(1 \le N \le 1000\)
• \(1 \le A[i] \le 10^{6}\)