Maximum Atiguous Sum of a Sequence(Array)

Let me first explain what the question is.

Given an array(a sequence of non-negative integers), we need to find that subsequence of this sequence such that:
1. No element in the subsequence is adjacent to any other element in that subsequence in the original array(atiguous).
2. The sum of the elements of this subsequence is the maximum for any subsequence of the array which satisfies (1).

I was asked this question in an interview but was able to come up only with a very inefficient solution for it. That solution consisted of enumerting all possible subsequences which satisfied (1) and find the one that gave the maximum sum. Only after a week did I come up with a solution that is Linear in complexity, and examines each element of the array just once.

I present it below and leave it up to the reader to modify the solution so that it works for negative integers as well. Hint: In case all the numbers are negative, the solution will contain no elements and the value of the maximum atiguous sum will be zero(0).

But before I present the solution, let me discuss how I got to it.
For the longest time, i was under the impression that the only solution that could exists would be the one that consisted of enumerating all sets with atiguous elements. However, on thinking more on it, it seemed that the solution could be improved because if you see, you must choose 2 out of every 4 contiguous elements, whatever way you look at it. Also, you may choose 1 or 2 out of 3 contiguous elements. Similarly, you could choose 0 or 1 out of 2 continuous elements. This means that in the worst case we will have a solution consisting of abs(N/2) elements for a sequence of N elements, and in the best case we have a solution consisting of abs((N+1)/2) elements.

If you solve this problem using the enumeration method, but continuously adding elements to a smaller sub-sequence, you will notice that the best solution involves choosing either the sum 2 elements later or the sum 3 elements later; adding it to the current element, and saving the maximum of these 2 values as the maximum sum up to the current element with the current element as a constituent. At the end of this exercise, the final solution is the maximum of the 1st or 2nd element(considering that we are working backwards).

import java.util.*;

public class MaxAtigSum {

    static private Vector
    getIntegers()
    {
        Vector ret = new Vector();
        Scanner sin = new Scanner(System.in);
        while (sin.hasNextInt())
        {
            Integer val = sin.nextInt(); 
            ret.add(val);    
        }
        
        return ret;
    }
    
    public static void main(String[ ] args)
    {
        Vector ints = getIntegers();
        Vector soln = new Vector();
        
        // Pad the array with 3 integers more than the ints array.
        System.out.println("Size of input: " + ints.size());
        for (int i = 0; i < ints.size() + 3; ++i)
        {
            soln.add(0);
        }

        for (int i = soln.size() - 4; i >= 0; --i)
        {
            soln.set(i, ints.get(i) + Math.max(soln.get(i+2), soln.get(i+3)));
        }

        System.out.println("The maximum atiguous sum is: " + Math.max(soln.get(0), soln.get(1)));     
        
    }
}

Update (22/06/2010): This is probably the first and last time I hope to write Java code. Such a verbose and ungainly language have I never seen.