Python Program for Kadane’s Algorithm
Kadane’s Algorithm in Python
Here, on this page, we will discuss the program for Kadane’s Algorithm in Python programming language
We are given an array and we need to find the largest contiguous subarray sum which can be done using Kadane’s algorithm efficiently.
Kadane’s Algorithm can be viewed both as greedy and DP. As we can see that we are keeping a running sum of integers and when it becomes less than 0, we reset it to 0 (Greedy Part). This is because continuing with a negative sum is way worse than restarting with a new range. Now it can also be viewed as a DP, at each stage we have 2 choices: Either take the current element and continue with the previous sum OR restart a new range
- Initialize a variable max_so_far and store maximum of the given array
- Iterate using a for between 0 to length of array -1 by i
- Initialize a variable s to store ith element of the array
- Run a nested for loop using variable j from i+1 to length of array
- Increment the value of s by arr[j]
- Check if s is greater than max_so_far if true store s to max_so_far
- After loop ends max_so_far stores the answer
def fun(arr, l): max_so_far = max(arr) for i in range(l - 1): s = arr[i] for j in range(i + 1, l): s += arr[j] if s > max_so_far: max_so_far = s return max_so_far array = [-2, -3, 4, -1, -2, 1, 5, -3] print("Largest contiguous subarray sum is :", fun(array, len(array)))
Largest contiguous subarray sum is : 7
For similar Questions click on the given button.