Max Subarray Brute Force Algorithm

[Brian Wells]

All,

FYI, I have developed an O(n^2) brute force algorithm for the Max Subarray problem. Please see below.

Thanks,

Brian

package divideAndConquer.maxSubarray;

public class BruteForceMaxSubarray_Brian extends MaxSubarrayAlgorithm{

    @Override

    public Solution findMaxSubarray(int[] A) {

        BruteForceMaxSubarray_Brian.Solution s = new BruteForceMaxSubarray_Brian.Solution();

        int maxsum = 0;

        s.sum = Integer.MIN_VALUE;

        for (int i = 0; i < A.length-1; i++) {

            maxsum += A[i];

            for (int j = i+1; j < A.length; j++) {

                maxsum += A[j];

                if (maxsum > s.sum) {

                    s.sum = maxsum;

                    s.leftIndex = i;

                    s.rightIndex = j;

                }

            }

            maxsum = 0;

        }

        return s;

    }

    

}

[Haidong (Haydon) Xue]

It is a faster and correct brute-force one, thx.

--
Haidong(Haydon) Xue
Ph.D Candidate
Research Assistant, Teaching Instructor
Department of Computer Science
Georgia State University

http://www.cs.gsu.edu/~hxue1

[Nick Mancuso]

O(n) time algorithm for max subarray in Python. Contains two algorithms (one simplified that is just DP to calculate the sum of the maximum subarray; other is to compute indices)

[Haidong (Haydon) Xue]

Thank you!

Yes, there are O(n) algorithms for it. The idea of the second algorithm is in 4.1-5. 

Some students asked me that why in Python brute-force MaximumSubarray is  O(n), so let me clarify:

0. They are not brute-force. (From where did you see that Nick said they are brute-force??????????) 

1. They are O(n) because they are different algorithms, not because they are in Python. 

2.  Most of the operations in an algorithm are independent on programming languages. 

3. Because of 2, in most of the cases, we say the time complexity of an algorithms is independent on the programming language implementing the algorithm.

Let me know if you have further questions.

[Nick Mancuso]

I didn't mean to cause confusion. I should have made it clearer that the "DP" in my email stood for "Dynamic Programming". The algorithm I sent is definitely not brute-force. As Haidong said, it is merely _another_ DP algorithm to compute maximum subarray. I wrote two versions of the O(n) algorithm, one to return the sum of the actual max subarray, and another to return the arguments (indices) for it. The reason I wrote it in Python is because I am most familiar with it. I should have stuck with Java for consistency.

Again, I apologize for any confusion I may have caused. The recurrence for the algorithm is given in these slides:

http://web.engr.oregonstate.edu/~glencora/other/tcscrashcourse.pdf

[Haidong (Haydon) Xue]

Thx, Nick. There is no fault at all. 

Many students may think algorithm complexity is dependent on the programming language that implements the algorithm. 

It results to a very good discussion here. 

[sneha v]

Thank you. This is very helpful !!

[shubham vyas]

If all the numbers are negative, it should return the largest negative number which is not happening with your code.