Recursion for max sum in array

Question

I have an array of numbers, A = [2,6,4,7,8,3,2,4,6,3]. I am trying to write an algorithm which recursively finds the max number in the array, however you once you select a number you need to skip the next two numbers. So for example if you pick the first number 2, you cant select 6 or 4, but you can select any number after that. So for example the solution for this array would be to pick the numbers 6,8,6 to make 20.

Answer 1

You can solve this problem either iteratively or recursively. The iterative solution would be more efficient.

A recursive solution in Java might look like following (not checking for empty arrays):

private int maxSumGap(int[] array, int gap, int start) {
  // Basis case is the start position is at the last position of the array
  if (start == array.length - 1;) {
    // Maximum is the only value
    return array[start];
  
  // Case if there are values after the gap
  } else if (start < array.length - 1 - gap) {
    // Compare the recursive calls with start position + 1 with the sum of start
    // position + 1 + gap plus the value at the start position
    return Math.max(
            maxSumGap(array, gap, start + 1),
            maxSumGap(array, gap, start + gap + 1) + array[start]
    );
  // Case if there are no values after the gap
  } else {
    // Compare the recursive calls with start position + 1 with the value at the
    // start position
    return Math.max(
            maxSumGap(array, gap, start + 1),
            array[start]
    );
  }
}