LPIS - Longest Perfect Increasing Subsequence


Dhrubo has a sequence of N integers. He is trying to find the longest perfect increasing subsequence of that sequence. But he is not very expert in finding longest perfect increasing subsequences. So he needs your help.

 A subsequence is a sequence that can be derived by another sequence by deleting elements without changing the order of the remaining elements. An increasing subsequence of a sequence is a subsequence where the elements are sorted in increasing order.

Difference between an increasing subsequence and a perfect increasing subsequence is that in a perfect increasing subsequence the difference between any two consecutive elements is always 1.

 For example, let’s consider a sequence S= {5, 2, 6, 3, 7, 8, 4}

{5, 3, 4} is subsequence of sequence S but not an increasing subsequence.

{5, 7, 8} is an increasing subsequence of sequence S, but not a perfect increasing subsequence.

But {5, 6, 7, 8} is perfect increasing subsequence as the difference between any two consecutive elements is exactly 1.

Note that, a single element will always be perfect increasing subsequence. So {5}, {2}, {7} are also perfect increasing subsequence of S.

INPUT:

First line of the input contains an integer N (1<=N<=105) denoting the length of the sequence.

Next line contains N integers separated by space which is the sequence.  These integers will be greater than 0 and will not be greater than 106.

OUTPUT:

A single integer in a line denoting the length of the longest perfect increasing subsequence.

Sample Input: #1

9

5 1 5 6 2 3 8 7 4

 

Sample Output: #1

4

 

Sample Input: #2

8

2 2 1 3 5 4 5 6

 

Sample Output: #2

5

 

( set by : Nashir Ahmed )


hide comments
cryp_bipul17: 2021-04-05 18:03:30

Solving it using dp but getting wa on test case 12

s_tank00_: 2020-08-22 12:47:34

solved using map in 0.25 sec
do anyone know any more optimal approach?

Last edit: 2020-08-22 12:49:24
be_legend: 2020-05-27 22:23:08

AC in one go. cakewalk!!
easy version of longest increasing subsequence.

pandey101299: 2020-02-03 05:41:11

easy one but careful about what is mean perfectly in this question.

sythe: 2020-02-01 17:06:39

Easy one!!!

sakshamdrose: 2019-12-12 12:41:25

Wrong answer on test case 10
Need some test cases

Rohit: 2019-10-21 21:55:52

Easy accepted in first go.

aryan29: 2019-09-12 00:54:06

siLLY mistake not initializing ma=0 get me 2 WA easy one

khan_cse_ruet: 2019-05-07 13:24:39

after a 2 hours thinking :v
Got O(n) solution.AC:)

mpride44: 2018-12-18 06:33:55

Finally AC in 0.00 sec with O(n) time complexity!!!

Last edit: 2018-12-18 06:36:23

Added by:Md. Najim Ahmed
Date:2015-12-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY