Maximum subarray problem brute force complexity

What is the runtime/memory complexity of the Maximum subarray 开发者_如何学JAVAproblem using brute force?

Can they be optimized more? Especially the memory complexity?

Thanks,

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.

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