LargestSumContiguousSubarray.java

/**
 * 
 * Write an efficient C program to find the sum of contiguous
 *  subarray within a one-dimensional array of numbers which has the largest sum.
 * @author paveynganpi
 *
 */


public class LargestSumContiguousSubarray {
	
	public static int solution(int[] arr){
		
		int maxSoFar=arr[0];
		int maxEndingHere=arr[0];
		
		for(int i=0;i<arr.length;i++){
			
			maxEndingHere = Math.max(arr[i], maxEndingHere+arr[i]);
			maxSoFar = Math.max(maxSoFar, maxEndingHere);
			System.out.println(maxSoFar +  "  " + maxEndingHere);
			
		}
		
		return maxSoFar;
		
		
	}
	
	public static void main(String[]args){
		
		int[] arr= {-2,-3,4,-1,-2,1,5,-3,-3,-4,-5,1};
		
		System.out.println(solution(arr));
	}

}