java - 数组中负整数元素的最小总和，可以选择跳过元素但没有两个连续的元素

Question

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

{-1,-3,-4,-10,-2​​2,-2}

我试图找到最接近 0 的和。允许跳过数字但不能连续。 IE。在上面的示例中，可能性是 -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();
     }
 }

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