Kadane’s Algorithm – Maximum sum subarray

public class KadaneAlgo {
	public static void main(String args[]){
		int[] inputArray={-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
		maxSubArray(inputArray);
		
	}

	public static void maxSubArray(int[] inputArray) {
		int cumulativeSum = 0;
		int maxSum = Integer.MIN_VALUE;
		int startIndex = 0;
		int endIndex = 0;
		int startIndexUntilNow = 0;

		for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
			cumulativeSum += inputArray[currentIndex];
			if (cumulativeSum > maxSum) {
				maxSum = cumulativeSum;
				startIndex = startIndexUntilNow;
				endIndex = currentIndex;
			}
                        if (cumulativeSum < 0) {
				startIndexUntilNow = currentIndex+1;
				cumulativeSum = 0;
			}
		}
		System.out.println("MaxSum : "+maxSum);
		System.out.println("Start Index : "+startIndex);
		System.out.println("End Index : "+endIndex);
	}

}


Leave a Reply

Your email address will not be published. Required fields are marked *