Table of Contents
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.
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.
When you run above program, you will get below output:
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// 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; } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
/* 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<arr.length;i++){ maxEndHere = Math.max(arr[i], maxEndHere+arr[i]); maxSoFar = Math.max(maxSoFar,maxEndHere); } return maxSoFar; } |
Kadane Algorithm in java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
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<arr.length;i++){ maxEndHere = Math.max(arr[i], maxEndHere+arr[i]); maxSoFar = Math.max(maxSoFar,maxEndHere); } return maxSoFar; } public static void main(String args[]) { int arr[] = { 1, 8, -3, -7, 2, 7, -1, 9 }; MaximumSubArrayMain maxSum = new MaximumSubArrayMain(); System.out.println("Maximum subarray is " + maxSum.kandaneForMaxSubArray(arr)); int arrNeg[] = { -10, -8, -3, -7, -2, -7, -3, -9 }; System.out.println("Maximum Subarray when all elements are negative : " + maxSum.kandaneForMaxSubArrayForNegativ(arrNeg)); } } |
|
1 2 3 4 |
Maximum subarray is 17 Maximum Subarray when all elements are negative : -2 |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
Hi Arpit, I have found this site very useful to practice programming.