Kadane's Algorithm

Kadane's Algorithm



TL;DR

  • This algorithm is used to find maximum sum sub-array from a given array. 
  • Its has O(n) time complexity and O(1) space complexity.  
  • It works irrespective of whether the elements are positive or negative, whether sorted or unsorted. 
  • Its DP approach
  • Its brute force approach takes O(n^2) as it calculates all possible sub-array and then return maximum out of them. 


Since brute force approach is very obvious and easy to implement, so, I am not discussing it here.

Lets directly jump to Kadane's Algorithm : 


Its uses two variables one stores local maximum ( local_maximum ) and other stores global maximum ( global_maximum ) .
Initialise , local_maximum = 0 and global_maximum = -Infinity 


We start iteration from the first element, and for each element we check following condition before updating the local_maximum :
  • if  local_maximum < 0 ,  then local_maximum = arr[i] ,  this is because if local_maximum is negative value then adding it with current value will result into lower value.
    Otherwise, if local_maximum >=0 then local_maximum= local_maximum + arr[i] .
Now, we got local_maximum till current element, its time to compare it with global_maximum . 
 
  • If global_maximum < local_maximum then  global maximum = local_maximum              
 
 Thats it, now after whole iteration is finished the our answer is the value of global_maximum. 


 

Now, its time to code it out : 

Language used : JavaScript 

var maxSubArray = function(nums) {
    var local_maximum=0;
    
    return nums
        .reduce( (global_maximum,current_element)=>{
        
        if(local_maximum <0 ) {
            local_maximum = current_element ;
        }
        else
            local_maximum = local_maximum + current_element ;
        
        global_maximum =  Math.max(global_maximum,local_maximum);
        
        return global_maximum ;
        
    }, -Infinity);
};


Please read about reduce function in JS if you don't already know about it. 



Comments

Post a Comment

Popular posts from this blog

HackerRank Problem : Reverse and capitalise first alphabet of each word.

  Problem : ( Link : Click here to visit this problem on HackerRank. ) Reverse the words in a string and capitalize the first letter of each reversed word, preserving the capitalization in the original stri. For eg: "Hello World" would be transformed to "OlleH DlroW". Input : The first line of input would be the number of test cases followed by each string in a line. Output : Output should be the string with each word reversed and first letter of each reversed word capitalized. Each output string should be printed to a new line.   Sample Input Sample Output 1 Hello World OlleH DlroW ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Solution : ( in C++ ) #include   <iostream> #include   <string> #include   <algorithm> #include   <cctype> using   namespace std ...
Keep reading

CodeChef : Breaking Bricks || Problem Code: BRKBKS

CodeChef : https://www.codechef.com/JAN20B/problems/BRKBKS Problem: For her next karate demonstration, Ada will break some bricks. Ada stacked three bricks on top of each other. Initially, their widths (from top to bottom) are W1,W2,W3. Ada's strength is S. Whenever she hits a stack of bricks, consider the largest k≥0 such that the sum of widths of the topmost k bricks does not exceed S; the topmost k bricks break and are removed from the stack. Before each hit, Ada may also decide to reverse the current stack of bricks, with no cost. Find the minimum number of hits Ada needs in order to break all bricks if she performs the reversals optimally. You are not required to minimise the number of reversals. Input The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows. The first and only line of each test case contains four space-separated integers S, W1, W2 and W3. Output For each test case, pri...
Keep reading

LeetCode: 169 Majority Element

LEETCODE : 169. Majority Element Link :  https://leetcode.com/problems/majority-element/ Problem Description :  Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. For example: Example 1: Input: [3,2,3] Output: 3   Example 2: Input: [2,2,1,1,1,2,2] Output: 2       ______________________________________________________________________________     Explaination :  There is pretty easy way to solve it by using count of every element and then returning the element which has count greater than n/2 . But this solution comes with a cost of O(n) time and O(n) space.  There is a better solution which can do the job in O(n) time and O(1) space. Atleast we are saving some of the space.  How does our space efficient algor...
Keep reading