Striver’s SDE Sheet Journey – #4 Kadane’s Algorithm

Hi👋Devs,

In the previous post, we have solved and understood the Next Permutation problem and in this post, we will tackle the next one Kadane’s algorithms.

#4 Kadane’s Algorithms

in this problem we have given an integer array nums, find t…


This content originally appeared on DEV Community and was authored by sachin26

Hi👋Devs,

In the previous post, we have solved and understood the Next Permutation problem and in this post, we will tackle the next one Kadane’s 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. if sum > max then max = sum.
3. if sum < 0 then sum = 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.

kadane's algorithms

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 to arrSize.

1. sum = sum + nums[i].
2. if sum > max then max = sum,lastIndex = i.
3. if sum < 0 then sum = 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 using firstIndex and lastIndex variable

  • elements of the max subarray.
    by traversing from firstIndex to lastIndex 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.


This content originally appeared on DEV Community and was authored by sachin26


Print Share Comment Cite Upload Translate Updates
APA

sachin26 | Sciencx (2021-12-21T11:13:17+00:00) Striver’s SDE Sheet Journey – #4 Kadane’s Algorithm. Retrieved from https://www.scien.cx/2021/12/21/strivers-sde-sheet-journey-4-kadanes-algorithm/

MLA
" » Striver’s SDE Sheet Journey – #4 Kadane’s Algorithm." sachin26 | Sciencx - Tuesday December 21, 2021, https://www.scien.cx/2021/12/21/strivers-sde-sheet-journey-4-kadanes-algorithm/
HARVARD
sachin26 | Sciencx Tuesday December 21, 2021 » Striver’s SDE Sheet Journey – #4 Kadane’s Algorithm., viewed ,<https://www.scien.cx/2021/12/21/strivers-sde-sheet-journey-4-kadanes-algorithm/>
VANCOUVER
sachin26 | Sciencx - » Striver’s SDE Sheet Journey – #4 Kadane’s Algorithm. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/12/21/strivers-sde-sheet-journey-4-kadanes-algorithm/
CHICAGO
" » Striver’s SDE Sheet Journey – #4 Kadane’s Algorithm." sachin26 | Sciencx - Accessed . https://www.scien.cx/2021/12/21/strivers-sde-sheet-journey-4-kadanes-algorithm/
IEEE
" » Striver’s SDE Sheet Journey – #4 Kadane’s Algorithm." sachin26 | Sciencx [Online]. Available: https://www.scien.cx/2021/12/21/strivers-sde-sheet-journey-4-kadanes-algorithm/. [Accessed: ]
rf:citation
» Striver’s SDE Sheet Journey – #4 Kadane’s Algorithm | sachin26 | Sciencx | https://www.scien.cx/2021/12/21/strivers-sde-sheet-journey-4-kadanes-algorithm/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts