Why is the maximum amount of sub-barrier brute force O (n ^ 2)?

Question

the maximum amount of subaram is a known problem in computer science.

There are at least two solutions:

• Brute force, find all possible auxiliary arrays and find the maximum.
• Use the Karanes algorithm parameter to calculate the global maximum when passing the first pass of the array.

In the video tutorial, the author mentions that the brute force method O(n^2), reading a different answer, one person thinks he O(n^2)is and the other thinks heO(n^3)

Is brute force O(n^2)or O(n^3)? And more importantly, can you illustrate what kind of analysis you performed using brute force to know it O(?)?

Answer 1

Well, it depends on how brute force is.

If we generate all the pairs (i, j): i <= jand calculate the sum between them, this 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 from all positions and calculate the current amounts, these are 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;
    }
}

Answer 2

. solve1() O (N) , solve2() O (N ^ 2), solve3() O (N ^ 3). , solve1() .

O (N ^ 2) O (N ^ 3) , O (N ^ 2) , end , O (N ^ 3), start end.

, , .

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);  
    }
}

:

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

Answer 3

O (N), !!! - ?

    int[] arr = {}; //elements;
    int max = 0, temp = 0;
    for (int i = 0; i < arr.length; i++) {
        temp = Math.max(arr[i], arr[i] + temp);
        max = Math.max(temp, max);
    }
    System.out.println(max); //result