Max Sum Contiguous Subarray

Feb 3, 2017

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example:
Given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
For this problem, return the maximum sum.

                
public class Solution {
    public int maxSubArray(final List a) {
        int size = a.size();
        if(size < 1){
            return 0;
        }else{
            int maxSoFar = 0;
            int totalMax = a.get(0);
            for(int i=0; i totalMax){
                    totalMax = maxSoFar;
                }
                if(maxSoFar < 0){
                    maxSoFar = 0;
                }
            }
            return totalMax;
        }
    }
}