Optimal algorithm for finding max value

Question

I need to design an algorithm to find the maximum value I can get from (stepping) along an int[] at predefined (step lengths).

Input is the number of times we can "use" each step length; and is given by n2, n5 and n10. n2 means that we move 2 spots in the array, n5 means 5 spots and n10 means 10 spots. We can only move forward (from left to right).

The int[] contains the values 1..5, the size of the array is (n2*2 + n5*5 + n10*10). The starting point is int[0].

Example: we start at int[0]. From here we can move to int[0+2] == 3, int[0+5] == 4 or int[0+10] == 1. Let's move to int[5] since it has the highest value. From int[5] we can move to int[5+2], int[5+5] or int[5+10] etc.

We should move along the array in step lengths of 2, 5 or 10 (and we can only use each step length n2-, n5- and n10-times) in such a manner that we step in the array to collect as high sum as possible.

The output is the maximum value possible.

public class Main {

private static int n2 = 5;
private static int n5 = 3;
private static int n10 = 2;
private static final int[] pokestops = new int[n2 * 2 + n5 * 5 + n10 * 10];

public static void main(String[] args) {

    Random rand = new Random();
    for (int i = 0; i < pokestops.length; i++) {
        pokestops[i] = Math.abs(rand.nextInt() % 5) + 1;
    }
    System.out.println(Arrays.toString(pokestops));
    //TODO: return the maximum value possible
}
}

Answer 1

This is an answer in pseudocode (I didn't run it, but it should work).

fill dp with -1.

dp(int id, int 2stepcount, int 5stepcount, int 10stepcount) {
  if(id > array_length - 1) return 0;
  if(dp[id][2stepcount][5stepcount][10stepcount] != -1) return dp[id][2stepcount][5stepcount][10stepcount];
  else dp[id][2stepcount][5stepcount][10stepcount] = 0;
  int 2step = 2stepcount < max2stepcount? dp(id + 2, 2stepcount + 1, 5stepcount, 10stepcount) : 0;
  int 5step = 5stepcount < max5stepcount? dp(id + 5, 2stepcount, 5stepcount + 1, 10stepcount) : 0;
  int 10step = 10stepcount < max10stepcount? dp(id + 10, 2stepcount, 5stepcount, 10stepcount + 1) : 0;
  dp[id][2stepcount][5stepcount][10stepcount] += array[id] + max(2step, 5step, 10step);
  return dp[id][2stepcount][5stepcount][10stepcount];
}

Call dp(0,0,0,0) and the answer is in dp[0][0][0][0].

If you wanna go backwards, then you do this:

fill dp with -1.

dp(int id, int 2stepcount, int 5stepcount, int 10stepcount) {
  if(id > array_length - 1 || id < 0) return 0;

  if(dp[id][2stepcount][5stepcount][10stepcount] != -1) return dp[id][2stepcount][5stepcount][10stepcount];
  else dp[id][2stepcount][5stepcount][10stepcount] = 0;

  int 2stepForward = 2stepcount < max2stepcount? dp(id + 2, 2stepcount + 1, 5stepcount, 10stepcount) : 0;
  int 5stepForward = 5stepcount < max5stepcount? dp(id + 5, 2stepcount, 5stepcount + 1, 10stepcount) : 0;
  int 10stepForward = 10stepcount < max10stepcount? dp(id + 10, 2stepcount, 5stepcount, 10stepcount + 1) : 0;

  int 2stepBackward = 2stepcount < max2stepcount? dp(id - 2, 2stepcount + 1, 5stepcount, 10stepcount) : 0;
  int 5stepBackward = 5stepcount < max5stepcount? dp(id - 5, 2stepcount, 5stepcount + 1, 10stepcount) : 0;
  int 10stepBackward = 10stepcount < max10stepcount? dp(id - 10, 2stepcount, 5stepcount, 10stepcount + 1) : 0;

  dp[id][2stepcount][5stepcount][10stepcount] += array[id] + max(2stepForward, 5stepForward, 10stepForward, 2stepBackward, 5backForward, 10backForward);
  return dp[id][2stepcount][5stepcount][10stepcount];
}

But your paths don't get fulled explored, because we stop if the index is negative or greater than the array size - 1, you can add the wrap around functionality, I guess.