/*
	Kadane's Algorithm to print largest contiguous array sum 
*/
import java.util.*; 

class Kadane 
{ 
	public static void main (String[] args) 
	{ 
		int [] a = {-20, -13, 6, 0, -12, 41, 39, -3}; 
		
		System.out.println("Maximum contiguous sum is " + maxSubArraySum(a)); 
	} 

	static int maxSubArraySum(int a[]) 
	{ 
		int size = a.length; 
		int max_so_far = Integer.MIN_VALUE, max_ending_here = 0; 

		for (int i = 0; i < size; i++) 
		{ 
			max_ending_here = max_ending_here + a[i]; 
			if (max_so_far < max_ending_here) 
				max_so_far = max_ending_here; 
			if (max_ending_here < 0) 
				max_ending_here = 0; 
		} 
		return max_so_far; 
	} 
}