All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Help Katekar
/

2-D, Algorithms, Arrays, DP, Dynamic programming

Problem
Editorial
Analytics

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}\)

 

SAMPLE INPUT
5
1 2 2 3 3
SAMPLE OUTPUT
3
Explanation

One possible subsequence is {1,2,2}.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?