Understanding algorithm for maximum sum of non-consecutive elements There is a well-known problem in CS of finding the maximum sum of non-consecutive integers in a list. There is even an SO post about how to solve it:

https://stackoverflow.com/questions/4487438/maximum-sum-of-non-consecutive-elements

That said, I have read this post many times, and many other posts online about how to solve this problem, and I still do not understand why the solution is correct.

Following another post about the problem (that shows the solution, but again lacks in an explanation as to why the solution is correct), I created the following snippit to run in JShell:

class MaxSubset {
    public static Integer maxSum(final List&lt;Integer&gt; ints) {
        final class MaxSubsetR {
            private Integer maxSumR(final List&lt;Integer&gt; ints, final Integer i, final String str) {
                if(i == 0) {
                    System.out.println("in i == 0: " + str);
                    System.out.println("in i == 0: get i " + ints.get(i) + " " + str);
                    System.out.println("in i == 0: get 0 " + ints.get(0) + " " + str);
                    System.out.println("returning: " + ints.get(0)); 
                    return ints.get(0); 
                }

                if(i == 1) {
                    System.out.println("in i == 1: " + str);
                    System.out.println("in i == 1: get i " + ints.get(i) + " " + str);
                    System.out.println("in i == 1: get 0 " + ints.get(0) + " " + str);
                    System.out.println("in i == 1: get 1 " + ints.get(1) + " " + str);
                    System.out.println("returning: " + Math.max(ints.get(0), ints.get(1)));
                    return Math.max(ints.get(0), ints.get(1));
                }
                System.out.println("no match " + i + " " + str);
                return Math.max(maxSumR(ints, (i - 1), "left"), ints.get(i) + maxSumR(ints, (i - 2), "right"));
            }
        }
        return new MaxSubsetR().maxSumR(ints, ints.size() - 1, "init");
    }
}


but after running the algorithm and watching the output, I'm still just as confused as I was when I began.

Can someone explain this algorithm to me? In particular:

1) How is the alternation of choosing (i - 1) or (i - 2) is even determined in the recursion in the first place?

2) How does simply subtracting 1 or 2 from the size of the array create the effect of selecting the optimal subset of non-adjacent items?

3) And just generally, how is it going about picking the right items from the list to achieve the stated goal?

New Question

4) We note that the List&lt;Integer&gt; never mutates during the recursion, so for the two if statements, i == 0 will always return the first item in the list, regardless of list size, and the i == 1 case will always return the greater of the first or second item in the list, regardless of list size. So, how is it that every item in the list is even being considered, if the return statements literally only care about arr[0] and arr[1]?

EDIT NOTES

I have re-written my second question to, hopefully, make it more clear what I mean.

For ease of reading, here is the algorithm in pseudo-code, without print statements:

func maxSum(Int[] arr, Int i)
  if(i == 0) return arr[0]
  if(i == 1) return Math.max(arr[0], arr[1])
  return Math.max(maxSum(arr, (i - 1)), maxSum(arr, (i - 2)) + arr[i])


and it would be called with

maxSum(arr, arr.size - 1)
Let me try to explain how to solve the problem. You are looking for a set of non-consecutive array elements with a maximum sum. 

Let's say you have an array of 100 elements. Which ones of elements #99 and #100 can be in the optimal solution? They cannot both be present, because they would be consecutive. They cannot both be absent, because then adding #100 would create a larger sum without violating the rules. So one of #99 and #100 is present, and the other is not. 

If #99 is present, then the solution is also the optimal solution for 99 elements. If #100 is present, then the items without #100 would be the optimal solution for 98 elements. So there are two possible ways to get an optimal solution for 100 elements: You take the optimal solution for 98 elements and add #100, or you take the optimal solution for 99 elements. 

So f (A, n) = max (f (A, n-1), f (A, n-2) + A[n]) if n ≥ 2; f (A, 1) = A[1] and f (A, 0) = 0. 

Note that implementing this using recursion is horribly inefficient. It's best to calculate f (A, 1), f (A, 2), f (A, 3) in sequence in linear time.