Sherlock and Cost Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<bits/stdc++.h>usingnamespacestd;intdp[100001][2];// dp[i][0]represents 1 was selected previously dp[i][1] represents that b[i-1] was selected previouslyintsolve(inti,intchoice,vector<int>&b,intn){if(i==n)return0;if(dp[i][choice]!=-1)returndp[i][choice];intans1,ans2;if(choice){ans1=abs(b[i]-b[i-1])+solve(i+1,1,b,n);ans2=abs(1-b[i-1])+solve(i+1,0,b,n);returndp[i][choice]=max(ans1,ans2);}else{ans1=abs(b[i]-1)+solve(i+1,1,b,n);ans2=abs(1-1)+solve(i+1,0,b,n);returndp[i][choice]=max(ans1,ans2);}}intmain(){intt,n;cin>>t;while(t--){cin>>n;vector<int>b(n);for(inti=0;i<n;i++)cin>>b[i];if(n==1)cout<<0<<"\n";elseif(n==2)cout<<b[1]-1<<"\n";else{for(inti=0;i<=n;i++){for(intj=0;j<2;j++)dp[i][j]=-1;}cout<<max(solve(1,0,b,n),solve(1,1,b,n))<<"\n";}}return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and Cost
You are viewing a single comment's thread. Return to all comments →