Maximum subarray problem brute force complexity

Question

What is the runtime/memory complexity of the Maximum subarray problem using brute force?

Can they be optimized more? Especially the memory complexity?

Thanks,

Dissertation

The algorithm is on the page you linked too so you could just inspect that to get the answer? – Molten

The algorithm in the page is not implemented via brute force. It is an O(n) and O(1) space algorithm. In fact I am not interested in this specific problem. It is just that the complexity analysis of the brute force approach to this problem is similar to many other problems in CS. – Dissertation

Given that you have to examine every item in the array at least once, it's not possible to do better than O(n). And, since you have to keep a running total, at least O(1) additional space is required. I'd say that the algorithm can't be improved. However, it's almost certainly possible to optimize the implementation. – Fireside

Answer 1

Brute force is Omega(n^2). Using Divide and conquer you can do it with Theta(n lg n) complexity. Further details are available in many books such as Introduction to Algorithms, or in various resources on the Web, such as this lecture.

Reprobate

brute force algorithm for finding a maximum sum has O(n**3) complexity, see max_sum_subsequence, so it is reasonable to assume that brute force for finding a maximum subarray can't have a better complexity. – Alys

Answer 2

As suggested in this answer you can use Kadane's algorithm which has O(n) complexity. An implementation in Java:

public int[] kadanesAlgorithm (int[] array) {
        int start_old = 0;
        int start = 0;
        int end = 0;
        int found_max = 0;

        int max = array[0];

        for(int i = 0; i<array.length; i++) {
            max = Math.max(array[i], max + array[i]);
            found_max = Math.max(found_max, max);
            if(max < 0)
                start = i+1;
            else if(max == found_max) {
                start_old=start;
                end = i;
                }
        }

        return Arrays.copyOfRange(array, start_old, end+1);
    }

Monovalent