Kadanes-algorithm

It took me a while to understand the question , the kadanes algorithm is so work based on 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]

the subarrays can be

[2],[3],[-8],[7]

[2,3],[3,-8],[-8,7]

[2,3,-8],[3,-8,7]

[2,3,-8,7]

*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)

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

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