Given an array of integers for example, [1 4 3 2 9 8 7 6] Each integer represents an amount of money you can pick up. You are traveling through the array, and you can pick up the money. Every time you pick up some money, you must travel another X amount (minInterval) in order to pick up more money. – that is you must wait X travels in order to pick up any more money. What is the maximum amount of money you can pick up given the minInterval.

note: each travel is essentially just moving to the next index. you want to maximize the value of the money you pick up.

for example, if the minimum interval is 4 an optimal path would be,

What is a good algorithm to accomplish this? It’s basically an optimization problem.

## Advertisement

## Answer

you can use the dynamic programming to solve the problem. traverse the array from the last element to first,then you will have two choices for each element:

1.choose the current element ,transit from the i+x th element `dp[i]=dp[i+x]+a[i]`

2.don’t choose the current element,transit from `dp[i+1]`

,which means the max value you can get from interval `[i+1,n]`

then you can get:`dp[i]=max(dp[i+1],dp[i+x]+a[i])`

so:

#include <bits/stdc++.h> using namespace std; int main() { int n,x; cin>>n>>x; vector<int> a(n+1); vector<int> dp(n+1+x); for(int i=1;i<=n;++i) cin>>a[i]; for(int i=n;i>=1;--i){ dp[i]=max(dp[i+1],dp[i+x]+a[i]); } cout<<dp[1]<<endl; return 0; }

**3**People found this is helpful