import java.util.*;
 
class Ideone{
	public static void main(String[] args){
		int[] a = { -2, 3, -16, 100, -4, 5 };
		System.out.println("Maximum contiguous subarray sum => "+ maxContiguousSum(a));
 
		int[] b = { -2, 11, -4, 13, -5, 2 };
		System.out.println("Maximum contiguous subarray sum => "+ maxContiguousSum(b));
	}
 
	private static int maxContiguousSum(int[] a){
		int max_so_far = 0;
		int max_ending_here = 0;
 
		for(int i=0; i<a.length; i++){
			max_so_far = max_so_far + a[i];
			if(max_so_far > max_ending_here){
				max_ending_here = max_so_far;
			}else if(max_so_far < 0){
				max_so_far = 0;
			}
		}
		return max_ending_here;
	}
}