数组中两个连续数的最大和

Question

你是一个电视游戏节目的参与者，这给了你赢得奖金的机会。在游戏中，你会看到一系列框，每个框都包含一个允许你看到的正整数值。你有机会选择任何数量的盒子。您的总奖金是您选择包含的所有盒子的总和。这个游戏只有一个限制：如果你选择了两个连续的盒子，你不允许在总数中添加任何后续的盒子，而你的奖品是截至该点的累计金额。你的目标是最大化你的奖金。

给定一个正整数数组，代表游戏中呈现给你的每个盒子的值，返回你能赢得的最大奖励。

输入：[1, 4, 2, 10]

产出：14

输入：[1,4,5,3]

产出：9

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

我在第二个测试中一直失败。我尝试过DP解决方案，但结果还是一样的？任何帮助都将不胜感激。

Answer 1

你贪婪的方法是正确的，但是我发现你目前的解决方案有一些问题。

首先，对于大小为1的输入，您的程序将崩溃，因为您的第一个循环将假设输入至少为2。

接下来，你没有办法参考之前做出的决定。在tempMax中，基本上存储box[i]box[i 1]，因为每次迭代都会从tempMax中删除box[i-1]。

一种方法是为每次迭代存储两个值：如果选择框i，一个表示当前i之前的最大值，如果不选择i，一个表示最大值。请注意，您应该只考虑选择两个连续的框，如果它们是最后两个框，或者后面的框只包含0。这种见解允许您轻松计算前一次迭代的两个值。最后别忘了检查一下是不是该考虑增加两个连续的盒子了。

编辑：添加了解决方案

import java.lang.Math;

public class Game {
    public static int solution(int[] boxes) {
        int end = boxes.length;
        for(; end > 0 && boxes[end-1] == 0; end--);
        int max0 = 0, max1 = 0;
        for(int i = 0; i < end; i++) {
            int max0_new, max1_new;
            max0_new = Math.max(max0, max1);
            if(i == end-1) {
                max1_new = Math.max(max0, max1) + boxes[i];
            } else {
                max1_new = max0 + boxes[i];
            }
            max0 = max0_new;
            max1 = max1_new;
        }
        return Math.max(max0, max1);
    }

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

Answer 2

如果解决方案是返回两个最大值的总和，那么你所需要做的就是对数组进行排序，然后在数组的末尾选择两个值，或者按照相反的顺序排序，选择前两个值。

public static void main(String[] args) {
    Integer[] arr1 = {1, 4, 2, 10};
    Integer[] arr2 = {1, 4, 5, 3};
    
    List<Integer> list1 = Arrays.asList(arr1);
    List<Integer> list2 = Arrays.asList(arr2);
    
    Collections.sort(list1, Collections.reverseOrder());
    Collections.sort(list2, Collections.reverseOrder());
    
    System.out.println("Max sum for arr1: " + (list1.get(0) + list1.get(1))); // returns 14
    System.out.println("Max sum for arr2: " + (list2.get(0) + list1.get(1))); // returns 9
}

Answer 3

由于在考虑是否向分数中添加特定方框时，有三种不同的可能性，因此在探索所有分支时，我会使用递归来保持简单（加上从末尾开始工作并记录这些分数，以便更好地处理大量输入）：

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