Scribd
Upload
4 views

M1 Divide&Conquer - Maximum subarray sum

The document discusses the maximum subarray sum problem, which involves finding the contiguous subarray within a 1-D array that has the largest sum, even when the array contains both negative and positive numbers. It outlines a divide and conquer algorithm that operates in O(N log N) time, detailing the steps to find the maximum subarray sum in the left half, right half, and across the midpoint. An example is provided with the input array [-3,2,3,4,-4,-1], where the maximum subarray is [2,3,4] with a sum of 9.

Uploaded by

luckymlcvl
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views

M1 Divide&Conquer - Maximum subarray sum

The document discusses the maximum subarray sum problem, which involves finding the contiguous subarray within a 1-D array that has the largest sum, even when the array contains both negative and positive numbers. It outlines a divide and conquer algorithm that operates in O(N log N) time, detailing the steps to find the maximum subarray sum in the left half, right half, and across the midpoint. An example is provided with the input array [-3,2,3,4,-4,-1], where the maximum subarray is [2,3,4] with a sum of 9.

Uploaded by

luckymlcvl
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Maximum subarray sum

Thursday, December 1, 2022 8:25 PM

• To find maximum subarray sum (contiguous) of given 1-D array. Array may contain
negative and positive numbers which makes this a difficult problem. Brute force will take
O(N^2) time while a divide and conquer approach will take O(N log N) time.
• If all the array entries were positive, then the maximum-subarray problem would present no
challenge, since the entire array would give the greatest sum.
• Example : input array = [-3,2,3,4,-4,-1].
• here maximum subarray is [2,3,4]. hence maximum subarray sum is 9.

• Divide and Conquer Algorithm


1. Divide an array in two halves.
2. Find maximum subarray sum in left half.
3. Find maximum subarray sum in right half.
4. Find maximum subarray sum which crosses the midpoint.
5. Maximum of step 2,3 and 4 is our answer.

Left_Right_MaximumSubarray(A,l Midpoint_Crosssum(A,low,
ow,high) mid,high)
sum=0
if high==low // base case
return A[low] leftsum=-∞
else for i=mid downto low
mid=(low + high)/2 sum=sum+A[i]
leftsum=Left_Right_MaximumSubar if sum>leftsum
leftsum=sum
ray(A,low,mid)
rigthsum=Left_Right_MaximumSub sum=0
rightsum=-∞
array(A,mid+1,high)
midcrosssum=Midpoint_Crosssum( for i=mid+1 to high
sum=sum+A[i]
A,low,mid,high)
return if sum>rightsum
rightsum=sum
maximum(leftsum,rightsum,midcros
ssum) return leftsum+rightsum
endfunction endfunction

• Time complexity of Merger sort is 𝑇(𝑛) = 2𝑇 ⎯ + 𝜃(𝑛), 𝑛 > 1. 𝑇(1) = 1.


• Using Master Theorem: a=2 b=2 and f(n)=n. 𝑛 = 𝑛 = 𝑛 = 𝑛.
• Case 2: 𝑓(𝑛) ∈ 𝜃(𝑛 𝑙𝑜𝑔 𝑛) where k=0 therefore 𝑇(𝑛) ∈ 𝑂(𝑛 𝑙𝑜𝑔 𝑛) =
𝑶(𝒏. 𝒍𝒐𝒈. 𝒏).

Divide and Conquer Page 1


Divide and Conquer Page 2

You might also like