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