DEV Community

Cover image for Kadanes-algorithm
Abirami Prabhakar
Abirami Prabhakar

Posted on

Kadanes-algorithm

#beginners #python #dsa

It took me a while to understand the question , the kadanes algorithm is used to find the maximum sum of an subarray

now the real question is What is a subarray ?

a subarray is an array within a array that can start or end anywhere but must contain continous elements that make an array together , the longest subarray is the entire array itself and a

an array can have n * (n + 1) / 2

example
for an array

arr = [2, 3, -8, 7]
Enter fullscreen mode Exit fullscreen mode

the subarrays can be

[2],[3],[-8],[7]
[2,3],[3,-8],[-8,7]
[2,3,-8],[3,-8,7]
[2,3,-8,7]
Enter fullscreen mode Exit fullscreen mode

*Approach *

the approch to find the solution is different in *Kadanes-algorithm is by contining an array from previous array * that way it is less time consuming

current_sum = max(arr[i], current_sum + arr[i])
max_sum = max(max_sum, current_sum)
Enter fullscreen mode Exit fullscreen mode

the algorithm for

max -> first element <- current element
the array is put in a for loop

def maxSubArraySum(arr):
        max_sum = arr[0]
        current_sum = arr[0]

        for i in range(1, len(arr)):
            current_sum = max(arr[i], current_sum + arr[i])
            max_sum = max(max_sum, current_sum)

        return max_sum
Enter fullscreen mode Exit fullscreen mode

Note :

you might wonder , what will happen *if the max sum of the arr becomes negative in the loop It is dropped *

to sum up you could say the simple concept of kadanes algorithm works by

keep adding until it hurts (negative), then restart

Top comments (0)