Algorithm

problem link- https://www.spoj.com/problems/LPIS/

LPIS - Longest Perfect Increasing Subsequence

#dynamic-programming #adhoc

 

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.

Example

Input #1:
9
5 1 5 6 2 3 8 7 4

Output #1:
4
Input #2:
8
2 2 1 3 5 4 5 6

Output #2:
5

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

n = int(input())
dp = [0] * 1000002
ans = 1
for i in map(int, input().split(' ')):
    dp[i] = max(dp[i], dp[i - 1] + 1)
    ans = max(ans, dp[i])
print(ans)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
9
5 1 5 6 2 3 8 7 4

Output

x
–
+
cmd
4

#2 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>
using namespace std;

//FOLD ME
namespace{
typedef long long LL;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef unsigned long long ULL;

//Macros
int CC_;
#define sf scanf
#define pf printf
#define PP cin.get();
#define NL cout<<endl;
#define all(container) container.begin(),container.end()
#define DC(x_) cout<<">>> "<<#x_<"\n";DA(x_.begin(), x_.end());
#define DD(x_) cout<<">>>>( "<<++CC_<<" ) "<<#x_<<": "<<x_<<endl;
#define SS printf(">_<LOOOOOK@MEEEEEEEEEEEEEEE<<( %d )>>\n",++CC_);
#define EXT(st_) cout<<"\n>>>Exicution Time: "<<(double)(clock()-st_)/CLOCKS_PER_SEC<<endl;
#define DM(MT,n_,m_)pf("Matrix %s:\n   ", #MT);for(int i_= 0;i_<m_;i_++)pf("%4d ", i_);NL;NL;for(int r_=0;r_<n_;r_++){pf("%2d ", r_);for(int c_= 0;c_<m_;c_++)pf("%4d ", MT[r_][c_]);NL}
#define mem(a_,b_)(a_, b_, sizeof(a_));


//constants
const double EPS= 1E-9;
const double PI= 2*acos(0.0);
const long long MOD= 1000000007;
}

const int sss= 1E6;

int a[21];
int N;
int MX= 0;

int lis(int x, int s, int prev){
    if(x < 0) return s;
    
    int p= lis(x-1, s, prev);
    int q= 0;
    if(a[x] < prev) q= lis(x-1, s+1, a[x]);
    
    return max(p,q);
}

void solve(void){
    int n;
    
    cin>>n;
    N= n;
    for(int i=0; i<n; i++)cin>>a[i];
    
    cout<< lis(n-1, 0, INT_MAX) <<endl;
}



int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("D:/input.txt", "r", stdin);
    solve();
    
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
9
5 1 5 6 2 3 8 7 4

Output

x
–
+
cmd
4
Advertisements

Demonstration

SPOJ Solution-Longest Perfect Increasing Subsequence-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python