subsequence of array with maximum sum (Kadane’s Algorithm)

This is given by Jay Kadane.

Problem Statement: In a given array, find out subarray such that the sum of its elements is maximum.

Lets take an array:
a[] = {-1,1,2,-3,3,-1,2,-2}
subarray with maximum sum is 4 i.e, {3,-1,2}

Note: If the array with all its elements are positives, then the result is the sum of all the elements. Say if a[]={1,2,3,4}, then result=10
Note: If the array with all its elements are negative, then the result is the minimum element of all the elements. Say if a[]={-1,-2,-3,-4}, then result=-1

The base rule here is that: include negative numbers if the Sum is greater than zero, if not then exclude negative numbers.

This algorithm uses dynamic programming concept to find the sum. what is dynamic programming? evaluate smaller problems first and use that smaller problems result to solve bigger problem.

/**
 * @author ntallapa
 *
 */
public class KadaneAlgorithm {

	/**
	 * Algorithm to find max subarray sum
	 * @param a array for which max subarray sum needs to be found
	 * @return max subarray sum
	 */
	public int maxSubArraySum(int a[]) {
		int totMaxSum = a[0];
		int currMaxSum = a[0];

		for (int i = 1; i < a.length; i++) {
			currMaxSum = a[i]>(currMaxSum+a[i])?a[i]:(currMaxSum + a[i]);
			totMaxSum = totMaxSum>currMaxSum?totMaxSum:currMaxSum;
		}
		return totMaxSum;
	}

	/**
	 * Test
	 * @param args
	 */
	public static void main(String[] args) {
		KadaneAlgorithm la = new KadaneAlgorithm();
		int a[] = {-1,1,2,-3,3,-1,2,-2};
		int max_sum = la.maxSubArraySum(a);
		System.out.println("Maximum contiguous sum is \n" + max_sum);
	}
}