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.