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
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
More...
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
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
More...