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);
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey