MaximumSubArray.java

public class MaximumSubArray {
	// Kadane algorithm
	public int kandane(int[] arrA) {
		int current_sum = 0;
		int max_sum = 0;
		for (int i = 0; i < arrA.length; i++) {
			current_sum += arrA[i];
			if (current_sum < 0) {
				current_sum = 0;
			}
			if (max_sum < current_sum) {
				max_sum = current_sum;
			}
		}
		return max_sum;
	}

	// Below modification will allow the program to work even if all the
	// elements in the array are negative
	public int KandaneModify(int[] arrA) {
		int current_sum = arrA[0];
		int max_sum = arrA[0];
		for(int i=1;i<arrA.length;i++){
			current_sum = Math.max(arrA[i], current_sum+arrA[i]);
			max_sum = Math.max(max_sum,current_sum);
		}
		return max_sum;
	}

	public static void main(String args[]) {
		int arrA[] = { 1, 2, -3, -4, 2, 7, -2, 3 };
		MaximumSubArray i = new MaximumSubArray();
		System.out.println("Maximum subarray is  " + i.kandane(arrA));
		int arrB[] = { -2, -3, -4, -2, -7, -2, -3,-11 };
		System.out.println("Maximum Subarray when all elements are negative : " + i.KandaneModify(arrB));
	}
}