Striver's SDE Sheet Journey - 4 Kadane's Algorithm
HiDevs,
In the previous post, we have solved and understood the Next Permutation problem and in this post, we will tackle the next one Kadanes algorithms.
#4 Kadane's Algorithms
in this problem we have given an integer array nums
, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example 1:
Input: nums
= [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums
= [1]
Output: 1
Solution
we can easily solve this problem using the kadane's algorithms.
lets discuss Kadane's algorithms step by step.
step-1 initialize three int variable sum = 0
,max = nums[0]
, arrSize = nums.length
.
step-2 run a loop from i = 0
to arrSize
.
1. sum = sum + nums[i].
2. ifsum > max
thenmax = sum
.
3. ifsum < 0
thensum = 0
.
step-3 return max
step-4 end
why reinitialize sum = 0
if sum < 0
?
negative-sum never contribute to maximum sum, so it is better to reinitialize sum to 0 and start adding from next element
before coding this algorithm in java, have a look at this image for a better understanding of this algo.
Java
class Solution { public int maxSubArray(int[] nums) { int sum = 0; int max = nums[0]; int arrSize = nums.length; for(int i=0; i < arrSize; i++){ sum = sum + nums[i]; if(sum > max){ max = sum; } if(sum < 0) { sum =0 } } return max;}}
But how? can we know,
length of the max subarray
start & end index of the max subarray
elements of the max subarray
so, for these, we can make two more int variables firstIndex
& lastIndex
that store the start & last index number of the max subarray and then do modification in the step-2.
step-2 run a loop from
i = 0
toarrSize
.1. sum = sum + nums[i].
2. ifsum > max
thenmax = sum
,lastIndex = i
.
3. ifsum < 0
thensum = 0
,firstIndex = i+1
.
using firstIndex
and lastIndex
variables, now we can answer the following questions.
length of the subarray.
subArrSize = lastIndex - firstIndex
start & end index of subarray.
by usingfirstIndex
andlastIndex
variableelements of the max subarray.
by traversing fromfirstIndex
tolastIndex
we can find the elements
Java
class Solution { public int maxSubArray(int[] nums) { int sum = 0; int max = nums[0]; int arrSize = nums.length; int firstIndex = 0,lastIndex = 0; for(int i=0; i < arrSize; i++){ sum = sum + nums[i]; if(sum > max){ max = sum; lastIndex = i; } if(sum < 0) { sum =0; firstIndex = i + 1; } } return max;}}
Time Complexity
running a for loop from 0 to arrSize.
so, O(arrSize) will be it's time complexity.
Space Complexity
the algo is not using any extra space, then O(1) will be its space complexity.
if you like this article please let me in the comment section.
if you find anything wrong in the post,plz correct me.
Thank you for reading.
Original Link: https://dev.to/sachin26/strivers-sde-sheet-journey-4-kadanes-algorithm-3ga7
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To