Submission for the 2013-05-03 UpFront Code Challenge

subarraychallenge.java

/*
UpFront Wichita Code Challenge
2013-05-03
Maximum Subarray

Using any language or technique, write a program that meets the following
criteria:

Given an array containing positive and negative integers return the sum of the
hihest value continuous set.

For example in the following array:
[-4,  5,  5, -7,  4, -1,  8, -6]
The maximum subarray value is 14 coming from the continuous set [5,  5, -7,  4, -1,  8].

For testing use the following arrays which are preceeded by their expected result:
14 = [-4,  5,  5, -7,  4, -1,  8, -6]
12 = [ 2, -3,  6,  5, -1,  2, -4,  3]
 8 = [ 2,  5, -8, -3,  8, -2, -9,  7]
12 = [-4, -3,  6,  6, -9,  4, -9,  8]
*/

class SubArrayTest
{
    public static void main (String[] args)
    {
        MyCollection c = new MyCollection(args);
        System.out.println(c.highestSum());
    }
}

class MyCollection
{
    protected int[] list;
    protected int listSize;

    public MyCollection(String[] args)
    {
        listSize = args.length;
        list = new int[listSize];
        int x = 0;
        for (String arg : args) {
            list[x++] = Integer.parseInt(arg);
        }
    }

    public int highestSum()
    {
        int highestSum = 0;

        // Say our list is 10 long we will first evaluate the 10 item list then
        // both 9 item lists, then all 8 item lists and so on down to
        // individual items. So for example we will get the sums of spans 0..9,
        // 0..8, 1..9, 0..7, 1..8, 2..9, and so on.
        int testSum;
        for (int size = listSize; size > 0; --size) {
            for (int start=0; start <= listSize - size; ++start) {
                testSum = sumFromXtoY(start, start + size - 1);
                if(testSum > highestSum) {
                    highestSum = testSum;
                }
            }
        }

        return highestSum;
    }

    protected int sumFromXtoY(int x, int y)
    {
        int sum = 0;
        for (int i = x; i <= y; ++i) {
            sum += list[i];
        }
        return sum;
    }
}