The Maximum-Subarray Problem

What is meant by the maximum sub-array problem is that we want to find the non-empty, contiguous sub-array of an array whose values have the largest sum. Following is a divide & conquer solution implemented for it using Java language.

/**
 *
 * @author Rajind
 */
public class MaximumSubarrayProblem {
    public static int[] maxSubArray(int[] A) {
        int newsum = A[0];
        int max = A[0];

        int low = 0;
        int high = 0;

        for(int i=1;i<A.length;i++){ 
            if(newsum+A[i] > A[i]){
                high++;
            }else{
                low = i;
                high = i;
            }

            newsum = Math.max(newsum+A[i],A[i]);
            max= Math.max(max, newsum);
        }

        int[] arr = new int[3];
        arr[0] = max;
        arr[1] = low;
        arr[2] = high;
        return arr;
    }

    public static void main(String args[]){
        int[] arr = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
        int []array = maxSubArray(arr);
        System.out.println("max: "+array[0]);
        System.out.println("low: "+array[1]);
        System.out.println("high: "+array[2]);
    }
}

~Rajind Ruparathna