**Kadane's algorithm**

Kadane's algorithm
consists of a scan through the array values, computing at each position the
maximum (positive sum) subarray ending at that position. This subarray is
either empty (in which case its sum is zero) or consists of one more element
than the maximum subarray ending at the previous position.

**Usage of Kadane's algorithm**

It is used to obtain the
maximum subarray sum from an array of integers.

**Pseudo code:**

Initialize: max_so_far = 0

max_ending_here = 0

Loop for each element of the array

max_ending_here
= max_ending_here + a[i]

if(max_ending_here
< 0)

max_ending_here = 0

if(max_so_far
< max_ending_here)

max_so_far = max_ending_here

return max_so_far

**Code in Java:**

import java.util.Scanner;

/* Class
kadane */

public class KadaneAlgorithm {

**/* Function to largest continuous sum */**

**public**

**static**

**int**

**maxSequenceSum(**

**int**

**[]**

**arr**

**) {**

**int**

**maxSoFar**

**=**

**arr**

**[0],**

**maxEndingHere**

**=**

**arr**

**[0];**

**for**

**(**

**int**

**i**

**= 1;**

**i**

**<**

**arr**

**.**

**length**

**;**

**i**

**++) {**

**/* calculate maxEndingHere */**

**if**

**(**

**maxEndingHere**

**< 0) {**

**maxEndingHere**

**=**

**arr**

**[**

**i**

**];**

**}**

**else**

**{**

**maxEndingHere**

**+=**

**arr**

**[**

**i**

**];**

**}**

**/* calculate maxSoFar */**

**if**

**(**

**maxEndingHere**

**>=**

**maxSoFar**

**) {**

**maxSoFar**

**=**

**maxEndingHere**

**;**

**}**

**}**

**return**

**maxSoFar**

**;**

**}**

public static void main (String[] args) {

int[] arr =
{8,6,5,-19,-24,2,8,9,14,-1,7};

int sum = KadaneAlgorithm.

*maxSequenceSum*(arr);
System.

*out*.println("Maximum Sequence sum is: "+ sum);
}

}

Output: Maximum Sequence sum is: 39

## No comments:

## Post a Comment