数组中最小负整数元素的总和，可以跳过元素但不能跳过连续的两个。

Question

给定一个负整数数组，例如：

{-1，-3，-4，-10，-22，-2}

我试图找到最接近0的总和。可以跳过数字，但不能连续。 例如，在上面的示例中，可能性为-1、-4、-22或-1、-3、-10、-2等。

上述数组的答案为-3、-10、-2=-15

我有一个使用递归的解决方案，但我想知道是否有人能想到我遗漏的更简单的解决方案？

 private static int maxSum(int in[]){
     return maxSum(in,0,in.length==1) ;
 }

 private static int maxSum(int in[], int off, boolean skipped){
     if(off == in.length){
         return 0;
     }
     else if(in.length - off >= 1){
         if(skipped){
             return in[off] + maxSum(in,off+1,false);
         }
         else{
             int w0 = maxSum(in,off+1,true);
             int wn0 = in[off] + maxSum(in,off+1,false);
             return Math.max(w0,wn0);
         }
     }
     else {
         throw new RuntimeException();
     }
 }

- Yoda Genes

---

我不理解这部分内容可以跳过，但不能连续...你说{-7,-1,-2,-6}应该得到-3；但是在最初的例子{-1,-3,-4,-10,-22,-2}中，为什么结果不是-4（前两个）？ - Eugene

如果选择前两个，那么你将跳过-4、-10、-22和-2。理论上你可以跳过-3，但是那样你就不能跳过-4了。这有意义吗？ - Yoda Genes

所以你本来可以选择例如：-1，-3，-4，-22，-2，如果它们符合要求的话，对吧？ - Eugene

是的，那是正确的。 - Yoda Genes

Answer 1

由于所有元素都是负数，而且您不能跳过连续的两个元素，最接近0的总和将是奇数索引元素的总和与偶数索引元素的总和之一（因为您要尽可能多地跳过元素）。

计算这两个总和并返回较大的那个：

private static int maxSum(int in[]) {
    int odd = 0;
    int even = 0;
    for (int i = 0; i < in.length; i++) {
        if (i%2 == 0) {
            even += in[i];
        } else {
            odd += in[i];
        }
    }
    return Math.max(odd,even);
}

为

System.out.println (maxSum(new int[]{-1,-3,-4,-10,-22,-2}));

它打印输出

-15

- Eran

---

很棒的回答，伙计。 - Melchizedek

@Eran 留下了这个问题“待回答”，结果发现你已经回答了 :) +1 - Eugene

好主意，但这在这种情况下行不通：System.out.println(maxSum(new int[]{-7,-1,-2,-6}));答案应该是-3。 - Yoda Genes

@YodaGenes 很好的发现。我没有考虑到这种情况。让我再想一想。 - Eran

Answer 2

就像Eran所说的一样（有点晚了），但是通过Java-8中的Stream API：

int[] x = { -1, -3, -4, -10, -22, -2 };

Map<Boolean, Integer> map = IntStream.range(0, x.length)
            .boxed()
            .collect(Collectors.partitioningBy(
                    i -> i % 2 == 0,
                    Collectors.summingInt(i -> x[i])));

    System.out.println(Math.max(map.get(Boolean.FALSE), map.get(Boolean.TRUE)));

- Eugene