Why is the maximum sum subarray brute force O(n^2)?

Question

The maximum subarray sum is famous problem in computer science.

There are at least two solutions:

1. Brute force, find all the possible sub arrays and find the maximum.
2. Use a variation of Karanes Algorithm to compute the global max while going through the first pass of the array.

In a video tutorial the author mentions the brute force method is O(n^2), reading another answer one person thinks it O(n^2) and another thinks it's O(n^3)

Is the brute force O(n^2) or O(n^3)? And more importantly can you illustrate what analysis you performed on the brute force method to know it's O(?)?

Answer 1

Here are three solutions to the maximum subarray sum problem. solve1() runs in O(N) time, solve2() runs in O(N^2), and solve3() runs in O(N^3). Note that solve1() is known as Kadane's algorithm.

The difference between the O(N^2) and O(N^3) functions is that in the O(N^2) function, the sum is computed implicitly every time the end index is incremented, while in the O(N^3) function, the sum is computed with a third explicit loop between start and end.

I've additionally added code to all three approaches to handle the case when all the input values are negative.

public class MaximumSubarraySum {

    /**
     * Solves the maximum subarray sum in O(N) time.
     */
    public static int solve1(int[] input) {

        int sum = input[0];
        int bestSum = sum;

        for (int i = 1; i < input.length; i++) {
            sum = Math.max(input[i], input[i] + sum);
            bestSum = Math.max(sum, bestSum);
        }

        return bestSum;
    }

    /**
     * Solves the maximum subarray sum in O(N^2) time. The two indices
     * 'start' and 'end' iterate over all possible N^2 index pairs, with 
     * the sum of input[start, end] always computed for every 'end' value. 
     */
    public static int solve2(int[] input) {

        int bestSum = -Integer.MAX_VALUE;

        for (int start = 0; start < input.length; start++) {

            // Compute the sum of input[start, end] and update
            // 'bestSum' if we found a new max subarray sum.

            // Set the sum to initial input value to handle edge case
            // of all the values being negative.
            int sum = input[start];
            bestSum = Math.max(sum, bestSum);

            for (int end = start+1; end < input.length; end++) {
                sum += input[end];
                bestSum = Math.max(sum, bestSum);
            }
        }

        return bestSum;
    }

    /**
     * Solves the maximum subarray sum in O(N^3) time. The two indices
     * 'start' and 'end' iterate over all possible N^2 index pairs, and
     * a third loop with index 'mid' iterates between them to compute 
     * the sum of input[start, end].
     */
    public static int solve3(int[] input) {

        int bestSum = -Integer.MAX_VALUE;

        for (int start = 0; start < input.length; start++) {

            for (int end = start; end < input.length; end++) {

                // Compute the sum of input[start, end] using a third loop
                // with index 'mid'. Update 'bestSum' if we found a new 
                // max subarray sum.

                // Set the sum to initial input value to handle edge case
                // of all the values being negative.
                int sum = input[start];
                bestSum = Math.max(sum, bestSum);

                for (int mid = start+1; mid < end; mid++) {
                    sum = Math.max(input[mid], input[mid] + sum);
                    bestSum = Math.max(sum, bestSum);
                }
            }
        }

        return bestSum;
    }


    public static void runTest(int[] input) {

        System.out.printf("\n");
        System.out.printf("Input: ");
        for (int i = 0; i < input.length; i++) {
            System.out.printf("%2d", input[i]);
            if (i < input.length-1) {
                System.out.printf(", ");
            }
        }
        System.out.printf("\n");

        int result = 0;

        result = MaximumSubarraySum.solve1(input);
        System.out.printf("solve1 result = %d\n", result);

        result = MaximumSubarraySum.solve2(input);
        System.out.printf("solve2 result = %d\n", result);

        result = MaximumSubarraySum.solve3(input);
        System.out.printf("solve3 result = %d\n", result);

    }


    public static void main(String argv[]) {

        int[] test1 = { -2, -3,  4, -1, -2, -1, -5, -3 };
        runTest(test1);

        int[] test2 = { -2, -3, -4, -1, -2, -1, -5,  3 };
        runTest(test2);

        int[] test3 = { -2, -3, -4, -1, -2, -1, -5, -3 };
        runTest(test3);

        int[] test4 = { -2, -3,  4, -1, -2,  1,  5, -3 };
        runTest(test4);  
    }
}

The output is:

Input: -2, -3,  4, -1, -2, -1, -5, -3
solve1 result = 4
solve2 result = 4
solve3 result = 4

Input: -2, -3, -4, -1, -2, -1, -5,  3
solve1 result = 3
solve2 result = 3
solve3 result = 3

Input: -2, -3, -4, -1, -2, -1, -5, -3
solve1 result = -1
solve2 result = -1
solve3 result = -1

Input: -2, -3,  4, -1, -2,  1,  5, -3
solve1 result = 7
solve2 result = 7
solve3 result = 7