lowest sum of negative integer elements in an array with the option to skip elements but no two consecutive

Question

Given an array of negative integers such as:

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

I am trying to find the sum closest to 0. It is permitted that numbers can be skipped but not consecutively. ie. in the above example, the possibilities are -1, -4, -22 or -1, -3, -10, -2 etc.

The answer to the above array is -3, -10, -2 = -15

I have a solution that uses recursion, but I was wondering if anyone can think of a simpler solution that I am missing?

 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

Since all the elements are negative, and you can't skip more than two elements in a row, the sum closest to 0 will either be the sum of all the odd indexed elements of the sum of all the even indexed elements (since you want to skip as many elements as you are allowed to).

Compute both of these sums and return the higher of them:

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

For

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

it prints

-15