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

June 3, 2013 Leave a comment

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

## Recent Comments