I am going to write here my explanation for the the maximum subarray problem which is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum.
Here we can find this subarray using different algorithms, Here I shall talk about two of them,
1) Divide and Conquer :
Time Complexity: O(n log n)
Algorithmic Paradigm: Divide and Conquer
Algorithmic Paradigm: Divide and Conquer
2) Kadane’s Algorithm :
Time Complexity: O(n)
Algorithmic Paradigm: Dynamic Programming
Algorithmic Paradigm: Dynamic Programming
1) Divide and Conquer :
This is a method of designing algorithms where we divide the problem into a number of
sub-problems of smaller size, and we conquer these sub-problems by solving them recursively, ( we keep sending it back for further division until they are a base case of the recursion )
Finally we combine the solutions of these sub-problems to get the required solution of the
actual problem.
Now we have an array ( lets call it A ) in which there exists a sub-array ( lets call it S )
whose sum is the maximum when compared to other sub-array's,
our objective is to find S's sum.
This subarray could either have the middle element of A ( lets call it mid ) in it or not.
thus we have two cases
1) when mid exists inside S :
if this is the case then we take the array and look at the rest of the array from mid's
here we have chosen A[3] to be the mid ( (7+0)/2 = 3.5 )
now to find S, we can break the problem further into 2 parts( the left half and the right half ), S will consist of 2
sub-arrays S1 and S2 where,
S1 is the maximum subarray in the left half from A[3] to A[0] and
S2 is the maximum subarray in the right half A[4] to A[7].
these two can be found by iteration, for S1 take A[3] alone then 3,2 then 3,2,1 keep doing this until we find the sum of all elements from mid till the first element (A[0]), all the while keeping track of the maximum sum so gained. so we will have the value of the max subarray in the left of mid ( including mid ) and we can repeat this with the remaining half of the array to find S2's sum.
In the following code I have implemented this leftsum is the S1's sum and rightsum is
S2's sum. we can thus return (leftsum+rightsum) as S's sum.
In the following code I have implemented this leftsum is the S1's sum and rightsum is
S2's sum. we can thus return (leftsum+rightsum) as S's sum.
# a is the array, start, mid and end are the respective array indices
def maxsubarray3(a,start,mid,end):
# if want to find the actual subarray which gives us this maximum value for its sum
ansstart=mid
ansend=mid+1
# we need to find both sums of the left maxsubarray and the right maxsubarray.
# the sum of which will be the sum of the joint subarray (from i to j) the actual max subarray of a
# where i and j are such that,
# The subarray from i to mid_index is the maximum you can get
# from all subarrays where i which is before mid_index
# keeps track of all the the possible subarray sums
tempsum=0
# keeps track of the current top sum (for the left half)
# initially keep it as a very negative number
leftsum=-1
# lets take first half and find the maximum subarray,
# start from mid and by decrementing ( therefore the -1 )
# and go till the 1st element ( therefore till array indice start )
# ( Note that the range(a,b,c) function produces a list of a,a+c,a+2c,.. so on till b-1 )
# ( we need to write start-1 to get till start )
for i in range(mid,start-1,-1):
tempsum=tempsum+a[i]
if(tempsum>leftsum):
# the new top sum
leftsum=tempsum
ansstart=i
# just like how we got the leftsum, repeat for right sum.
tempsum=0
rightsum=-1
# we now check for all possible subarrays in the right half, ie
# mid+1 till end ( Note that the range(a,b,c) function
# produces a list of a,a+c,a+2c,.. so on till b-1 )
for j in range(mid+1,end+1):
tempsum=tempsum+a[j]
if(tempsum>rightsum):
# the new top sum
rightsum=tempsum
ansend=j
return (rightsum+leftsum)
But we should keep in mind we have only covered the case when the max subarray we wish to find has the mid element in it, but then comes the other case.
2) when mid is not inside S :
In this case we can further divide this case by calling the same function recursively.
until it ends up as the case discussed above ora trivial case when the array becomes a single element.
I have implemented this with the following code.
# Actual function to solve the max subarray problem
def maxsubarray(a,start,end):
# Base case when recursion caused the array to finally become a single element
# the element itself is the only sum, therefore the maximum
if(start==end):
return a[start]
# find mid - an integer as its going to be used as a index
mid=int((start+end)/2)
# now we can find the maximum of the 3 cases
# we divide the array a into 2 parts (0 to mid) and (mid+1 to end), if the "maxsubarray" is a subarray of these 2 halfs we can find so by calling recursively
# else if the subarray we seek is that which crosses the middle element, then we call the maxsubarray3 function
return max(maxsubarray(a,start,mid),maxsubarray(a,mid+1,end),maxsubarray3(a,start,mid,end))
So we can see how this algorithm works. I hope. :p
