给定约束的数组中的最大和

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

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

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

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

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

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

一种方法是为每次迭代存储三个值：

• 如果我们选择当前框而不是前一个框的最大值（max0）
• 最大值，如果我们没有选择当前框，并且没有连续选择之前的迭代（max0）
• 最大值，如果我们选择当前框，而前一个框也被选中（max11）

编辑：添加解决方案

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