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;
}
0 Comments