HackerEarth Increasing Subsequence problem solution

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.

#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