Find the maximum-sum subarray of an array. OR
Explain Kadane's Algorithm to solve the Maximum Sum Subarray OR
Find Largest Sum Contiguous Subarray.
The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. |
| Max sum contiguous subarray solution |
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 than 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 than 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,
- maxSumTillNow, which will store max sum till now encountered.
- 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.
In 1st iteration, for arr[0], maxSumTillNow=4 and tempSum=4
In 2nd iteration, for arr[1], maxSumTillNow=4 and 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 and tempSum=4
In 2nd iteration, for arr[1], maxSumTillNow=4 and tempSum=2
In 3rd iteration, for arr[2], maxSumTillNow=4 and tempSum=8
In this case, our tempSum is greater than 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 and endIndex = 0
In 2nd iteration, for arr[1], maxSumTillNow=4, tempSum=2, startIndex = 0 and 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 and 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)
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 in maxSumTillNow, 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.
What is Hashmap data structure? What is the need of Hashmap? How Hashmap data structure works in Java? What is Hashcode? Can 2 objects have same hashcode?
How Hashmap data structure works internally? How hashcode and equals method is used in hashmap? Explain with real time example.
What is Load factor and Rehashing in Hashmap?
When get/put method of Hashmap goes to Infinite loop in HashMap?
Multithreading Interview Question Answers In Java
How ConcurrentHashMap works and ConcurrentHashMap interview questions
How Much Water Can A Bar Graph with different heights can Hold
Detect loop in linked list.
0/1 Knapsack Problem solved using Iterative and Dynamic Programming
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment