Here in this post we will learn about Kadane’s Algorithm, we will see its code and implement it.
Question For Kadane's Algorithm
Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.
Example For Kadane's Algorithm
Input:
N = 5
Arr[] = {1,2,3,-2,5}
Output:
9
Explanation:
Max subarray sum is 9
of elements (1, 2, 3, -2, 5) which
is a contiguous subarray.
Input:
N = 4
Arr[] = {-1,-2,-3,-4}
Output:
-1
Explanation:
Max subarray sum is -1
of element (-1)
Approach
The basic idea behind Kadane’s approach is to search the array for all positive contiguous segments (max ending here is utilized for this). Also, among all positive segments, maintain track of the greatest total contiguous segment (max so far is utilized for this). Each time we get a positive total, we compare it to max so far and update max so far if it’s larger.
Algorithm
Initialize:
max_so_far = INT_MIN
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 0
return max_so_farCode for Largest Sum of Contiguous Subarray
Python Code
from sys import maxsize
class Solution:
##Complete this function
#Function to find the sum of contiguous subarray with maximum sum.
def maxSubArraySum(self,arr,N):
##Your code here
max_so_far = -maxsize - 1
max_ending_here = 0
s = 0
for i in range(0,N):
max_ending_here += arr[i]
if max_so_far < max_ending_here:
max_so_far = max_ending_here
if max_ending_here < 0:
max_ending_here = 0
return max_so_far
arr = [-2,1, -3, 4, -1, 2, 1, -5, 4]
soln = Solution()
print(soln.maxSubArraySum(arr,len(a))
Time Complexity: O(n)
Auxiliary Space: O(1)
Python code to print largest sum with starting and ending index
# Largest Sum Contiguous Subarray
# https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
# Python program to print largest contiguous array sum
from sys import maxsize
# Function to find the maximum contiguous subarray
# and print its starting and end index
def maxSubArraySum(a,size):
max_so_far = -maxsize - 1
max_ending_here = 0
# to store the starting index from where subarray starts
start = 0
# to store the ending index from where subarray starts
end = 0
s = 0
#iterate over array
for i in range(0,size):
max_ending_here += a[i]
if max_so_far < max_ending_here:
max_so_far = max_ending_here
start = s
end = i
if max_ending_here < 0:
max_ending_here = 0
s = i+1
print ("Maximum contiguous sum is %d"%(max_so_far))
print ("Starting Index %d"%(start))
print ("Ending Index %d"%(end))
# Driver program to test maxSubArraySum
a = [-2,1, -3, 4, -1, 2, 1, -5, 4]
maxSubArraySum(a,len(a))
Output :-
Maximum contiguous sum is 6
Starting Index 3
Ending Index 6
