Maximize the amount of money you pick up as you travel through an array [closed]

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.

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