# 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 0using 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 1000000007using 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;}`