SP25893 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/A

N/A