import java.util.Scanner;

/**
 * Program to implement Kadanes Algorithm to 
 * calculate maximum contiguous subarray sum of an array
 * Time Complexity: O(n)
 * 
 * @author Nishita Aggarwal
 *
 */

public class KadaneAlgorithm {
	
	/**
	* This method implements Kadane's Algorithm
	* 
        * @param arr The input array
	* @return The maximum contiguous subarray sum of the array
        * 
        */
	static int largestContiguousSum(int arr[]){
		int i,len=arr.length,cursum=0,maxsum=Integer.MIN_VALUE;
		if(len==0)	//empty array
			return 0;
		for(i=0;imaxsum){
				maxsum=cursum;
			}
			if(cursum