Problem:
Given an integer array find the continuous sub array with the maximum sum in the array.
Input:
For example , consider the input
[5,-6,8,-4,-2,7,4,-1]
There are many possible continuous sub arrays in the above array [5],[5,-6] , [5,-6,8] , [-6,8,-4,-2] etc. The elements just need to be continuous as present in the initial array. Even a single element can be considered a sub array . The entire array can also be considered as one of the sub arrays.
You need to add the values of all the elements in a sub array and find out which subarray has the maximum sum
Output:
In the above case the maximum sub array is [8,-4,-2,7,4] with the sum 13. All other sub arrays have a value less than 13.
So output is 13
Try out the solution here:
https://leetcode.com/problems/maximum-subarray/
Solution:
The brute force solution to this problem is to iterate through the entire array and for each element in the array add subsequent elements in the array and calculate the sum noting the maximum sum at each addition.
This requires two nested for loops and the order of complexity is O(n2)
Here is the code:
public static int maxSubArray(int[] nums) {
//initialize max to first element
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
int sum = nums[i];
// compare first element if it is greater than max
if (sum > max) {
max = sum;
}
//add rest of the elements one by one and at each addition check //if the sum is greater than max
for (int j = i + 1; j < nums.length; j++) {
sum = sum + nums[j];
if (sum > max) {
max = sum;
}
}
}
return max;
}
A better solution of time complexity O(n) can be implemented using Kadane’s algorithm.
Hint:
The basic idea of Kadane’s algorithm is to find positive sub arrays (whose sum adds upto a positive value) and find the subarray with the maximum sum.
ALGORITHM:
STEP1: Initialize two variables , currentMax and max to 0. The currentMax refers to the sum of the current positive sub array and max refers to the sum of the largest positive sub array.
STEP2: For each element in the array , add the element to currentMax and assign it to currentMax itself
STEP2 a: If the above sum is less than 0, assign the value 0 to currentMax
STEP2 b: If currentMax calculated in STEP2 is greater than max assign max to currentMax
STEP3: Kadane’s algorithm works only if there is atleast one positive value in the array. To check this have a boolean variable and assign it to true if any element is positive (Do this along with the iteration mentioned in STEP 2)
STEP3 a: If there is any positive value as computed in STEP3 , find the maximum value from all the negative values and return it.
Let’s see how this works
Consider the array
input = [5,-6,8,-4,-2,7,4,-1]
let
i denote the index of each element
currentMax denote the sum of the current positive sub array
max denote the sum of the largest positive sub array
Iteration 1:
i=0 , input[0] = 5, currentMax = 0, max =0
currentMax = currentMax + input[0] = 0+5 = 5
It is a positive value , so assign it to currentMax, now currentMax = 5
This value is greater than max (initialized to 0) , so assign it to max , max = currrentMax = 5
Iteration 2:
i = 1; input[1] = -6, currentMax = 5, max = 5
currentMax = currentMax+input[1] = 5+(-6) = -1
It is a negative value , so assign 0 to currentMax , now currentMax = 0;
This value is less than max , hence max remains same , max = 5
Iteration 3:
i=2, input[2] = 8, currentMax = 0, max = 5
currentMax = currentMax+input[2] = 0+8 = 8
It is a positive value , so assign it to currentMax , now currentMax = 8;
This value is greater than max , hence max now becomes , max = 8
Iteration 4:
i=3 , input[3] = -4 , currentMax = 8 , max = 8
currentMax = currentMax + input[3] = 8 + (-4) = 4
It is a positive value , so assign it to currentMax , now currentMax = 4
This value is less than max , so max remains , max = 8
Iteration 5:
i = 4, input[4]= -2 , currentMax = 4, max = 8
currentMax = currentMax + input[4] = 4 + (-2) = 2
It is a positive value , so assign it to currentMax , now currentMax = 2
This value is less than max , so max remains , max = 8
Iteration 6:
i = 5, input[5] = 7 , currentMax = 2, max = 8
currentMax = currentMax + input[5] = 2+7 = 9
It is a positive value , so assign it to currentMax , now currentMax = 9
This value is greater than max , so max now becomes , max = 9
Iteration 7:
i =6, input[6] = 4, currentMax = 9, max = 9
currentMax = currentMax + input[6] = 9+4 = 13
It is a positive value , so assign it to currentMax , now currentMax = 13
This value is greater than max , so max now becomes , max = 13
Iteration 8:
i = 7, input[i] = -1 , currentMax = 13 , max = 13
currentMax = currentMax + input[7] = 13+(-1) = 12
It is a positive value , so assign it to currentMax , now currentMax = 12
This value is less than max , so max remains , max = 13
The iterations end and we return the max value , max = 13
Optimal Code:
Here is the code:
class Solution {
public int maxSubArray(int[] nums) {
int max = 0;
int currentMax = 0;
boolean anyPositive = false;
for(int i=0;i< nums.length;i++){
currentMax = currentMax + nums[i];
if(currentMax < 0){
currentMax = 0;
}
if(currentMax > max){
max = currentMax;
}
if(nums[i]>0){
anyPositive = true;
}
}
if(!anyPositive){
int negativeMax = nums[0];
for(int i=0;i<nums.length;i++){
if(nums[i] > negativeMax){
negativeMax = nums[i];
}
}
max = negativeMax;
}
return max;
}
}
That’s it!
Leave a Reply