HackerEarth Increasing Subsequence problem solution

YASH PAL, 31 July 202414 February 2026

In this HackerEarth Increasing Subsequence problem solution Given an array, A, having N integers, an increasing subsequence of this array of length k is a set of k indices i1,i2,…ik, such that 1 <= i1 < i2 < … ik <= N and A[i1] < A[i2] < A[i3] < … < A[ik].

Energy of a subsequence is defined as sum of difference of consecutive numbers in the subsequence. For a given integer k, you need to find out the maximum value of energy among energies of all increasing subsequences of length k.

HackerEarth Increasing Subsequence problem solution

HackerEarth Increasing Subsequence problem solution.

#include<bits/stdc++.h>
#define DEBUG 0
using namespace std;
vector< vector<int> > bit;
int n, k;
 
int query(int idx, int x){
    int ret = INT_MAX;
    while(x){
        ret = min(bit[idx][x], ret);
        x -= (x&(-x));
    }
    return ret;
}
 
void update(int idx, int x, int val){
    while(x <= n){
        bit[idx][x] = min(bit[idx][x], val);
        x += (x&(-x));
    }
}
vector< vector<int> > ans;
int a[1000010];
int rev[1000010];
int main(){
    cin>>n>>k;
    for(int i=0; i<=k; i++){
        vector<int> v;
        for(int j=0; j<=n; j++)v.push_back(0);
        bit.push_back(v);
        ans.push_back(v);
    }
    if(DEBUG)cout<<"here"<<endl;
    for(int i=0; i<=k; i++){
        for(int j=0; j<=n; j++)
            bit[i][j] = INT_MAX;
    }
    if(DEBUG)cout<<"here"<<endl;
    map<int, int> m;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        m[a[i]];
    }
    if(DEBUG)cout<<"here"<<endl;
    int cnt = 1;
    for(auto it:m){
        rev[cnt] = it.first;
        m[it.first]=cnt++;
    }   
    int mx = -1;
    for(int i=1; i<=n; i++){
        int x = m[a[i]];
        ans[1][x] = x;  
        update(1, x, x);
        for(int j=2; j<=k; j++){
            int res = query(j-1, x-1);  
            ans[j][x] = res;
            update(j, x, res);
        }
        if(ans[k][x] <= n)
            mx = max(mx, a[i]-rev[ans[k][x]]);
    }   
    cout<<mx<<endl;
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define INF 1000000007
using namespace std;
vector<vector<int> >bit;
int get(int index,int k)
{
    int ans=bit[k][index];
    while(index>0)
    {
        ans=min(ans,bit[k][index]);
        index-=index & (-index);
    }
    return ans;
}
void update(int index,int k,int val,int n)
{
    while(index<=n)
    {
        bit[k][index]=min(bit[k][index],val);
        index+= index & (-index);
    }
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<=k;i++)
    {
        vector<int>temp;
        for(int j=0;j<=n;j++)temp.push_back(j);
        bit.push_back(temp);
    }
    for(int i=0;i<=k;i++)for(int j=0;j<=n;j++)bit[i][j]=INF;
    map<int,int>mp;
    int a[n+5],ans=-1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ans=max(ans,a[i]);
        mp[a[i]]=1;
    }
    if(k==1){cout<<ans<<"n";return 0;}
    
    ans=-1;
    int l=1;
    map<int,int> :: iterator it;
    for(it=mp.begin();it!=mp.end();it++)
        it->second=l++;
 
    for(int i=1;i<=n;i++)
    {
        int ind=mp[a[i]],val;
        update(ind,1,a[i],l);
        for(int j=2;j<=k;j++)
        {
            val=get(ind-1,j-1);
            update(ind,j,val,l);
        }
        //cout<<val<<"n";
        ans=max(ans,a[i]-bit[k][ind]);
    }
    cout<<ans<<"n";
    return 0;
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply