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

Question

The maximum subarray sum is a 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 Kadane's 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

Well, it depends on how brute the force is.

If we generate all (i, j): i <= j pairs and calculate the sum between, it is O(n^3):

....
for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++) {
        int sum = 0;
        for (int k = i; k <= j; k++)
            sum += a[k];
        if (sum > max)
            max = sum;
    }

If we start at all positions and calculate running sums, it is O(n^2):

....
for(int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = i; j < n; j++) {
        sum += a[j];
        if (sum > max)
            max = sum;
    }
}