If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.
Kadane algorithm is a famous algorithm to solve maximum subarray problem.
Maximum subArray problem:
From Wikipedia :
In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
Kadane ‘s Algorithm can be used to solve maximum sub array problem
Kadane’s algorithm:
- Initialize maxSoFar= 0 and maxEndingHere = 0
- Iterate over each element of the array
- maxEndingHere = maxEndingHere + a[i]
- if(maxEndingHere < 0)
- maxEndingHere = 0
- if(maxSoFar < maxEndingHere)
- maxSoFar = maxEndingHere
- return maxSoFar
Java Code:
// Kadane's Algorithm
public int kandaneForMaxSubArray(int[] arr) {
int maxEndHere = 0;
int maxSoFar = 0;
for (int i = 0; i < arr.length; i++) {
maxEndHere += arr[i];
if (maxEndHere < 0) {
maxEndHere = 0;
}
if (maxSoFar < maxEndHere) {
maxSoFar = maxEndHere;
}
}
return maxSoFar;
}
Above algorithm won't work if all elements of array are negative. We will make small changes to algorithm to make it work for negative numbers for too.
Modified Kadane's algorithm:
- Initialize maxSoFar= arr[0] and maxEndingHere = arr[0]
- Iterate over each element of the array
- maxEndingHere =Max of (arr[i], maxEndHere+arr[i])
- if(maxSoFar < maxEndingHere)
- maxSoFar = maxEndingHere
- return maxSoFar
Java code:
/* Modified Kadane's algorithm
* If you make small modification to above algorithm
* It will work for negative numbers too
*/
public int kandaneForMaxSubArrayForNegativ(int[] arr) {
int maxEndHere = arr[0];
int maxSoFar = arr[0];
for(int i=1;i
Kadane Algorithm in java
package org.arpit.java2blog;
public class MaximumSubArrayMain {
/* Kadane algorithm
* It won't work when all elements of array are negative
*/
public int kandaneForMaxSubArray(int[] arr) {
int maxEndHere = 0;
int maxSoFar = 0;
for (int i = 0; i < arr.length; i++) {
maxEndHere += arr[i];
if (maxEndHere < 0) {
maxEndHere = 0;
}
if (maxSoFar < maxEndHere) {
maxSoFar = maxEndHere;
}
}
return maxSoFar;
}
/* Modified Kadane's algorithm
* If you make small modification to above algorithm
* It will work for negative numbers too
*/
public int kandaneForMaxSubArrayForNegativ(int[] arr) {
int maxEndHere = arr[0];
int maxSoFar = arr[0];
for(int i=1;i
When you run above program, you will get below output:
Maximum subarray is 17
Maximum Subarray when all elements are negative : -2
Hi Arpit, I have found this site very useful to practice programming.