Algorithm
Problem link- https://www.spoj.com/problems/DCEPC501/
DCEPC501 - Save Thy Toys
Leonard is very fond of buying rare and expensive science fiction toys. He keeps his collection in a sequential order of the date on which the toy was bought in a special closet so that his roomie Sheldon never gets hold of his toys. But because of his bad luck Leonard once loses a bet to Sheldon and Sheldon demands a share Leonard’s toys. Since Leonard doesn’t want to loose much money, he decides upon a strategy to reduce his loss to minimum.
Leonard, beginning from the first toy in his closet will pick some toys, say "x" toys in sequence. Sheldon will then pick the next "x" toys (Note that Sheldon picks equal no. of toys as picked by Leonard in his move unless the remaining toys are less than "x". In that case he picks all of the remaining). This will keep going on till no more toys are left in the closet for Leonard to pick. You are given the sequence of toys with their price. Help Leonard in maximizing the total price of all toys he picks.
Leonard in his each turn can either pick only 1 or 2 or 3 toys ("x" described above can take value either 1, 2 or 3).
Input
First line specifies T, the number of test cases.
Each test case contains N in the first line. Second line contains N integers as described above.
Output
Output 1 line for each test case giving the maximum possible value of the total sum of all toys Leonard picks.
Constraints
1<=T<=10
1<=N<=100000
1<=Price of toys<=1000000
Example
Input: 2 4 5 4 3 2 6 10 8 7 11 15 20 Output: 12 53
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e5+5;
ll arr[MAXN];
ll dp[MAXN];
ll solve(int idx){
if(idx < 0)
return 0;
if(dp[idx] != -1)
return dp[idx];
ll ans = 0;
ans = max(ans, arr[idx] + solve(idx-2));
if(idx-1 >= 0)
ans = max(ans, arr[idx] + arr[idx-1] + solve(idx-4));
if(idx-2 >= 0)
ans = max(ans, arr[idx] + arr[idx-1] + arr[idx-2] + solve(idx-6));
// ans = max(ans, solve(idx-1));
dp[idx] = ans;
return ans;
}
int main(){
io;
int t;
cin >> t;
while(t--){
memset(dp, -1, sizeof dp);
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> arr[i];
int l = 0, r = n-1;
while(l < r){
int temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
l++;
r--;
}
cout << solve(n-1) << endl;
}
return 0;
}Input
4
5 4 3 2
6
10 8 7 11 15 20
Output
53
Demonstration
SPOJ Solution-Save Thy Toys-Solution in C, C++, Java, Python