Problem Statement:

Given an array of positive integers, return the maximum sum.

There is only one limitation: if you pick two consecutive elements, you are not allowed to add any subsequent one to your total, and your sum is the amount accumulated up to that point. Your goal is to maximise your sum.

Example 1:

Input: [1, 4, 2, 10]

Output: 14

Example 2:

Input: [1, 4, 5, 3]

Output: 9

My solution:

  public static int solution(int[] boxes) {
    if(boxes.length == 0) {
      return 0; 
    }
    int tempMax = 0;
    
    for(int i = 0; i < 2; i  ) {
      tempMax  = boxes[i];
    }
    
    int max = tempMax;
    
    for(int i = 1; i < boxes.length - 1; i  ) {
      int sub = tempMax - boxes[i - 1];
      tempMax = sub   boxes[i   1];
      
      if(max < tempMax) {
        max = tempMax;
      }
    }
    
    return max;
  }

I keep failing on the first test case. I have tried a DP solution but that yielded the same results? Any help would be appreciated.

CodePudding user response：

Since there are three different possibilities when considering whether or not to add a particular box to the score, I'd use recursion to keep things simple when exploring all the branches (Plus working from the end and memoizing those scores to better handle huge inputs):

import java.util.Arrays;
import java.util.Random;

public class Demo {

    /** 
     * Find the maximum possible score of the given boxes
     *
     * @param boxes The boxes
     * @param i the index of the current box we're considering adding
     * to the score.
     * @param score the current score without the current box
     * @param cache already computed maximum scores starting with the
     * Nth box, or -1 if not already found.
     * @return the maximum possible score
     */
    private static int solve(int[] boxes, int i, int score, int[] cache) {
        if (i >= boxes.length) {
            // No more boxes to consider
            return score;
        } else if (cache[i] > -1) {
            // The maximum score for the current box to the end has
            // already been calculated; re-use it.
            return score   cache[i];
        } else if (i == boxes.length - 1) {
            // Last box; go ahead and add it to the score and we're done.
            return score   boxes[i];
        } else {
            /* Now there are three options with at least one more box
             * after this one: */

            // Add the current box and the next box, and then stop
            // (Two consecutive boxes).
            int s1 = score   boxes[i]   boxes[i   1];

            // Add the current box and skip a box to keep calculating
            // a score
            int s2 = solve(boxes, i   2, score   boxes[i], cache);

            // Skip the current box and keep calculating
            int s3 = solve(boxes, i   1, score, cache);
            
            // Now return the largest of the three
            return Math.max(s1, Math.max(s2, s3));
        }
    }
    
    private static int solve(int[] boxes) {
        int[] cache = new int[boxes.length];
        Arrays.fill(cache, -1);
        // Solve from the end - calculate the maximum score of the
        // last N boxes of the array. Then when calculating the score
        // for the N-1th box, that value can be re-used.
        cache[boxes.length - 1] = boxes[boxes.length - 1];
        for (int i = boxes.length - 2; i >= 0; i--) {
            cache[i] = solve(boxes, i, 0, cache);
        }
        return cache[0];
    }

    private static void show(int[] boxes) {
        System.out.println("Input: "   Arrays.toString(boxes));
        System.out.println("Output: "   solve(boxes));
    }

    /** Generate an array of random numbers for testing large inputs */
    private static void show(Random rng, int size) {
        show(rng.ints(1, 21).limit(size).toArray());
    }
    
    public static void main(String[] args) {
        Random rng = new Random();      
        show(new int[]{1, 4, 2, 10});
        show(new int[]{1, 4, 5, 3});
        show(rng, 1000);
    }
}

CodePudding user response：

Your greedy approach goes in the right direction, however I see a few issues with your current solution.

First off, your program will crash for inputs of size 1, since your first loop will assume that the input has at least size 2.

Next, you don't have a way to refer to previous decisions being made. In tempMax you basically store boxes[i] boxes[i 1], since with every iteration you remove boxes[i-1] from tempMax.

An approach would be to store three values for every iteration:

• The maximum if we select the current box and not the previous one (max0)
• The maximum if we don't select the current box and there are no consecutive selections for previous iterations (max0)
• The maximum if we select the current box when the previous box was also selected (max11)

Edit: Added solution

import java.lang.Math;

public class Game {
    public static int solution(int[] boxes) {
        int max0 = 0, max1 = 0, max11 = 0;
        for(int i = 0; i < boxes.length; i  ) {
            int max0_new = Math.max(max0, max1);
            int max1_new = max0   boxes[i];
            int max11_new = Math.max(max11, max1   boxes[i]);
            max0 = max0_new;
            max1 = max1_new;
            max11 = max11_new;
        }
        return Math.max(max0, Math.max(max1, max11));
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[]{1, 4, 2, 10}));
        System.out.println(solution(new int[]{1, 4, 5, 3}));
    }
}