MaxSubSum

/**
 * @author Sean Allred
 * @author Molly Domino
 *
 */
public class driver {

    // 2^n
    private static int SubSum(int arr[]) {
        int maxSum = 0;

        for (int startElement = 0; startElement < arr.length - 1; startElement++) {

            for (int endElement = startElement + 1; endElement < arr.length; endElement++) {

                int thisSum = 0;
                for (int thisElementIndex = startElement; thisElementIndex <= endElement; thisElementIndex++) {

                    thisSum += arr[thisElementIndex];
                }

                if (thisSum > maxSum)
                    maxSum = thisSum;
            }
        }

        for (int i : arr)
            if (i > maxSum)
                maxSum = i;

        return maxSum;

    }

    // n^3
    public static int subSum(int arr[]) {
        int maxSum = 0;
        int thisSum = 0;
        for (int startingElementIndex = 0;
                 startingElementIndex < arr.length;
                 startingElementIndex++) {
            for (int endingElementIndex = arr.length;
                     endingElementIndex > startingElementIndex;
                     endingElementIndex--) {
                for (int thisElementIndex = startingElementIndex;
                         thisElementIndex < endingElementIndex;
                         thisElementIndex++) {

                    thisSum += arr[thisElementIndex];
                    if (thisSum > maxSum)
                        maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

    private static int rand(java.util.Random r, int min, int max) {
        return r.nextInt(max - min + 1) + min;
    }

    public static void main(String[] args) {

        Integer s = Integer.parseInt(args[0]);

        int[] randArray = new int[s];

        java.util.Random randSeed = new java.util.Random();

        for (int i = 0; i < randArray.length; i++) {
            randArray[i] = rand(randSeed, -10, 10);
        }

        for (int T : randArray) {
            System.out.println(T);
        }

        System.out.print("Max Sum: " + SubSum(randArray));
    }

}