Kadane's Algorithm in Java to find Largest Sum Contiguous Subarray.
Kadane's Algorithm in Java. Kadane's Algorithm to solve maximum sum subarray problem.The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.
 |
| Kadane algorithm in Java |
Lets see what is expected output from given input,
Case 1:
Input:
{3, -1, -1, -1, -1, -1, 2, 0, 0, 0}
Output:
start index :0
End index :0
Sum :3
Case 2:
Input:
{-1, 3, -5, 4, 6, -1, 2, -7, 13, -3}
Output:
start index :3
End index :8
Sum :17
Case 3:
Input:
{-2,-3,4,-1,-2,1,5,-3}
Output:
start index :2
End index :6
Sum :7
Case 4:
Input:
{-1,3,-5,4,6,-1,2,-7,13,-3}
Output:
start index :3
End index :8
Sum :17
Case 5:
Input:
{-1}
Output:
start index :0
End index :0
Sum :-1
Case 6:
Input:
{-6,-2,-3,-4,-1,-5,-5}
Output:
start index :4
End index :4
Sum :-1
Algorithm: How to find maximum subarray sequence?
0 element Array
If there is no element present in array then we can say that,
in this case, startIndex = -1, endIndex = -1 and
maxSum = -1 (or any other suitable notation for no element present) 1 element Array
If array is having only one element, then that single element is the highest in array
as that is the only element present in array,
in this case, startIndex = 0, endIndex = 0 and maxSum = arr[0];
Now, lets look for array having length greater than 1.
Before iterating the array, we first check array length and if it is greater then 0,
then only proceed else return startIndex = -1, endIndex = -1 and maxSum = -1.
Lets take one variable for storing sum and initialize it to 0;
int tempSum = 0;
Lets start a loop from 0 to length of array,
we will pick the first element of array and check,
tempSum = tempSum + array[i];
If tempSum is less then 0,
It means there is no point in including or considering this element in maximum
sum sub array search as including this element will bring the tempSum to less then 0,
So ignore the element and go ahead for searching next element.
If tempSum is greater then 0,
It means there is a chance that including or considering this element can lead to
maximum sum sub array, as including this element is not bringing tempSum to less then 0,
So consider this element and go ahead for searching next element.
However, considering this element is not guaranteed to form a maximum sub array
as it can decrease the total sum which is not less then 0.
Eg: if the array is {4, -2}
So initially, when considering element at position 0.
we will get tempSum = 4 and it is greater then 0, so we are including it,
Now lets see element at position 1, we will get tempSum = 2 (4 + -2 = -2),
In this case tempSum = 2, which is not less then 0, so should we consider this????
we should consider this and give a try because chances are there that we may get
higher element at next position(Eg array: {4, -2, 4})
but in our case we don't have element at position 2, so what to do in this case,
So what we will do is we will take 2 variables,
1. maxSumTillNow, which will store max sum till now encountered.
2. tempSum, which will store max sum till now encountered and also take risk of
adding next element which may or may not increase the maxSumTillNow.
Lets try to map this variables in our example,
In 1st iteration, for arr[0]
maxSumTillNow=4
tempSum=4
In 2nd iteration, for arr[1]
maxSumTillNow=4
tempSum=2
So our maxSumTillNow will reflect the maximum sub array sum.
Lets see example {4, -2, 6},
In 1st iteration, for arr[0]
maxSumTillNow=4
tempSum=4
In 2nd iteration, for arr[1]
maxSumTillNow=4
tempSum=2
In 3rd iteration, for arr[2]
maxSumTillNow=4
tempSum=8
In this case, our tempSum is greater then maxSumTillNow and maxSumTillNow is stale,
so what we will do in this situation is,
when tempSum > maxSumTillNow, then we will re initialize maxSumTillNow = tempSum;
and maxSumTillNow gets updated.
Now when maxSumTillNow gets updated, obviously we have to update
startIndex and endIndex as new element get added to maxSumTillNow.
So by looking at this example, do we need to update start index when we include element 6?
Lets see example from start {4, -2, 6},
In 1st iteration, for arr[0]
maxSumTillNow=4
tempSum=4
startIndex = 0
endIndex = 0
In 2nd iteration, for arr[1]
maxSumTillNow=4
tempSum=2
startIndex = 0
endIndex = 0
In 3rd iteration, for arr[2]
maxSumTillNow=8
(in this case tempSum > maxSumTillNow, so maxSumTillNow is updated to
value of tempSum)
tempSum=8
startIndex = 0
endIndex = 2
We can see from above example, when our tempSum > maxSumTillNow,
we are including a new element in our chain, so our chain start element will remain same,
that is we don't need to update start index at this point but we need to update endIndex to
index position of new element added.
So when we will update startIndex then????
Let see one more example {4, -2, 6, -10, 8, 1},
In 1st iteration, for arr[0]
maxSumTillNow=4
tempSum=4
startIndex = 0
endIndex = 0
In 2nd iteration, for arr[1]
maxSumTillNow=4
tempSum=2
startIndex = 0
endIndex = 0
In 3rd iteration, for arr[2]
maxSumTillNow=8
tempSum=8
startIndex = 0
endIndex = 2
In 4th iteration, for arr[3]
maxSumTillNow=8
tempSum=-2
startIndex = ?
endIndex = ?
Now, when we encounter that our result was going good and next element when checked
is making tempSum to -2 that is tempSum < 0,
So in this case it is sure including this element(-10) in chain before this element(4, -2, 6)
will make the result negative, so not include this element in consideration and simply ignore
this element and keep our variables as it is without modification.
So our variables will be,
maxSumTillNow=8
tempSum=-2
startIndex = 0
endIndex = 2
we can see from this, that there forms 2 chain,
one chain is before -10 that is (4, -2, 6) and
one chain is after -10 that is (8, 1)
and -10 when included with before chain or after chain will surely decrease the result.
Now question is which chain contains maximum sub array sum, before -10 or after -10?
Till now we have seen before chain and we got maxSumTillNow=8 and variables as,
maxSumTillNow=8
startIndex = 0
endIndex = 2
Now, we will start exploring after chain, so before exploring after chain,
we have to reset variable tempSum to 0 as we are starting the things again.
So when tempSum<0, we will reset tempSum to 0.
Also, keeping existing startIndex = 0 and endIndex = 2 intact, we need to explore next chain.
So we have to take one more variable as tempStartIndex.
tempStartIndex holds new start index of new chain that we are going to explore.
When we found that new chain sum is greater then chain we already explored,
at that time we will update startIndex to tempStartIndex.
Also, when we observe tempSum<0, at that time we will initialize
tempStartIndex = i(currentIndex) + 1,
because next max chain we can get, can be formed excluding current element and start from
next index.
In 5th iteration, for arr[4]
maxSumTillNow=8
tempSum=8(from -2, reseted to 0 and now included element 8)
startIndex = 0
endIndex = 2
tempStartIndex = 4
In 6th iteration, for arr[5]
maxSumTillNow=8
tempSum=9
we can see in this step,
tempSum>maxSumTillNow, so we have to update maxSumTillNow as we got new chain
starting from tempStartIndex and ending at i(curent index)
So we will update variable startIndex to tempStartIndex value as that is the starting
place where we started exploring new chain.
also, we will update variable endIndex to i(current index of loop).
also, we will update variable maxSumTillNow to tempSum.
So the new variables are,
maxSumTillNow=9
tempSum=9
startIndex = 4
endIndex = 5
tempStartIndex = 4
Program to find the largest sum contiguous subarray in Java
In this program, instead of using 3 variables that we are interested inmaxSumTillNow, startIndex. and endIndex, we are using result array whose,
result[0] will represent startIndex,
result[1] will represent endIndex,
result[2] will represent maxSumTillNow
package javabypatel.kadane;
public class MaximumSubArray {
public static void main(String[] args) {
int[] arr = {-1,3,-5,4,6,-1,2,-7,13,-3};
int[] result = findMaxSumIndex(arr);
System.out.println("start index :"+result[0]);
System.out.println("End index :"+result[1]);
System.out.println("Sum :"+result[2]);
}
private static int[] findMaxSumIndex(int[] arr){
int[] result = new int[3];
int maxSumTillNow = Integer.MIN_VALUE;
int tempStartIndex = 0;
int tempSum = 0;
for (int i = 0; i < arr.length; i++) {
tempSum = tempSum + arr[i];
if(tempSum > maxSumTillNow){
maxSumTillNow = tempSum;
result[0] = tempStartIndex;
result[1] = i;
result[2] = maxSumTillNow;
}
if(tempSum<0){
tempSum = 0;
tempStartIndex = i + 1;
}
}
return result;
}
}
Time Complexity:
The runtime complexity of Kadane's algorithm is O(n) as we are iterating the array containing n elements only once.
You may also like to see
0/1 Knapsack Problem solved using Iterative and Dynamic Programming
Stock Buy Sell to Maximize Profit.
Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted
Count trailing zeros in factorial of a number.
How to Detect loop in linked list.
Tower Of Hanoi Program in Java.
Print Matrix Diagonally OR Diagonal order of Matrix.
Rotate Matrix by 90 degrees clockwise Inplace
Implement Queue using One Stack in Java (Recursive Implementation)
Count trailing zeros in factorial of a number.
Breadth First Search(BFS) Vs Depth First Search(DFS) with example in Java
When to use SOAP over REST Web Service. Is REST better than SOAP?.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment