Maximum sum in array given constraints

95
June 29, 2022, at 01:40 AM
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.

Answer 1

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);
    }
}
Answer 2

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}));
    }
}
Rent Charter Buses Company
READ ALSO
How can I remove a parameter from a subclass constructor in Java?

How can I remove a parameter from a subclass constructor in Java?

In my superclass, I have defined the parameters a, b, c and dFor its subclass, I want to remove d

87
Problem with concurrent sessions and OAuth2 in Spring Boot

Problem with concurrent sessions and OAuth2 in Spring Boot

I'm working with Spring Security 56

114
Pass html data to Quarkus Template

Pass html data to Quarkus Template

I am using Quarkus Mailer and Quarkus Template to create an endpoint that will be responsible just for sending emailsFor now it just receives the subject, body and the emails that the email should be sent to

107
Can I change a keystore JKS file&#39;s alias password with only the keystore password and not the alias password?

Can I change a keystore JKS file's alias password with only the keystore password and not the alias password?

Is it possible to change a keystore alias' password without having the oldI do have the keystore's password and the alias name

159