All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Help Katekar
Tag(s):

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

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

NIT Surat

Challenge Name

EPIPHANY 8.0

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?