Largest Sum Contiguous Subarray..

Reference: http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

public class MaxSubArray {

    /*
    Notes: Algorithm doesn't work for all negative numbers. It simply returns 0
    if all numbers are negative. For handling this we can add an extra phase
    before actual implementation. The phase will look if all numbers are negative,
    if they are it will return maximum of them (or smallest in terms of absolute
    value). There may be other ways to handle it though.
    */
    public int findMaxSubArray(int a[]){
        int max_so_far = 0;
        int max_ending_here = 0;
        for(int i=0; i<a.length; i++){
            max_ending_here += a[i];
            if(max_ending_here < 0)
                max_ending_here = 0;
            if(max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
        return max_so_far;
    }
 
    /*
     * Another implementation which takes care of all +ve as well as -ve value.
     */
    public int findMaxSubArray2(int a[]){
        int max_so_far = a[0];
        int current_max = a[0];
        for(int i=1; i<a.length; i++){
            current_max = Math.max(a[i], current_max+a[i]);
            max_so_far = Math.max(max_so_far, current_max);
        }
        return max_so_far;
    }
 
    public static void main(String args[]){
        MaxSubArray msa = new MaxSubArray();
        int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
        int res = msa.findMaxSubArray(a);
        System.out.println("MaxSum: " + res);
        int b[] = {-2, -3, -4, -1, -2, -1, -5, -3};
        res = msa.findMaxSubArray2(b);
        System.out.println("MaxSum2: " + res);
    }
}

# Output

MaxSum: 7

MaxSum2: -1