Kadane’s Algorithm is an O(n) algorithm for finding the maximum contiguous sub-sequence in a one-dimensional sequence.
The problem: given an array which could contain zero, negative, and positive numbers, find the largest sum of contiguous sub-array. For example, if the array contains:
-2,1,-3,4,-1,2,1,-5,4
the contiguous sub-array with the largest sum is 4, -1, 2, 1, with sum 6.
Kadane’s algorithm consists of a scan through the array values, computing at each position the maximum 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. Thus, the problem can be solved with the following code
package com.struts2spring;
public class Main {
boolean isAllElementNegative = true;
int maxSoFar = 0;
int maxUpToHere = 0;
int max = 0;
// This is our main method
public static void main(String[] args) {
int[] arr = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
Main m = new Main();
if (!(m.isAllElementNegative(arr))) {
System.out.println("the largest sum for contiguous sub-array is:" + m.lagestSum(arr));
} else {
m.max = arr[0];
for (int i = 0; i < arr.length; i++) {
m.max = m.max > arr[i] ? m.max : arr[i];
}
System.out.println("the largest sum for contiguous sub-array is:" + m.max);
}
}
// finding sum of contigous sub-array.
int lagestSum(int[] arr) {
for (int i = 0; i < arr.length; i++) {
maxUpToHere = max(maxUpToHere + arr[i], 0);
maxSoFar = max(maxSoFar, maxUpToHere);
}
return maxSoFar;
}
// To find max of two number.
int max(int first, int second) {
return first > second ? first : second;
}
// Checking all the element of an array is negative or not.
boolean isAllElementNegative(int[] arr) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0) {
return isAllElementNegative = false;
}
}
return isAllElementNegative;
}
}
References:
- Maximum subarray problem: wikipedia
struts2spring 