Downloaded 77 times
![Example… Here, the subarray A[8…11] is the Maximum Subarray, with sum 43, has the greatest sum of any contiguous subarray of array A.](https://image.slidesharecdn.com/d2216e5c-75da-44c5-ab56-829b21931b58-150413003852-conversion-gate01/75/The-Maximum-Subarray-Problem-3-2048.jpg)
![Divide and Conquer Solution • First we Divide the array A [low … high] into two subarrays A [low … mid] (left) and A [mid +1 … high] (right). • We recursively find the maximum subarray of A [low … mid] (left), and the maximum of A [mid +1 … high] (right). • We also find maximum crossing subarray that crosses the midpoint. • Finally we take a subarray with the largest sum out of three.](https://image.slidesharecdn.com/d2216e5c-75da-44c5-ab56-829b21931b58-150413003852-conversion-gate01/75/The-Maximum-Subarray-Problem-5-2048.jpg)
![Pseudo Code Max-subarray(A, Left, Right) if (Right == Left) return (left, right, A[left]) else mid= [(left+right)/2] L1=Find-Maximum-Subarray(A,left,mid) R1=Find-Maximum-Subarray(A,mid+1,right) M1=Find-Max-Crossing-Subarray(A,left,mid,right) If sum(L1) > sum(R1) and sum(L1) > sum(M1) Return L1 elseif sum(R1) > sum(L1) and sum(R1) > sum(M1) Return R1 Else return M1](https://image.slidesharecdn.com/d2216e5c-75da-44c5-ab56-829b21931b58-150413003852-conversion-gate01/75/The-Maximum-Subarray-Problem-8-2048.jpg)
Uploaded byKamran Ashraf
The Maximum Subarray Problem
The document discusses the maximum subarray problem and different solutions to solve it. It defines the problem as finding a contiguous subsequence within a given array that has the largest sum. It presents a brute force solution with O(n2) time complexity and a more efficient divide and conquer solution with O(nlogn) time complexity. The divide and conquer approach recursively finds maximum subarrays in the left and right halves of the array and the maximum crossing subarray to return the overall maximum.
In this document
Powered by AI
Introduction to the Maximum Subarray Problem, its definitions, and challenges with both positive and negative numbers.
Explains the brute force solution and its inefficiencies; introduces the Divide and Conquer method as a more efficient solution.
Analyzes the time complexity of the Divide and Conquer solution; establishes the running time as Θ(n log n).
Presents the pseudocode for the Max-Subarray function detailing recursive function calls and logic for finding the maximum subarray.
The Maximum Subarray Problem
- 1. The Maximum SubarrayProblem Defining problem , its brute force solution, divide and conquer solution Presented by: Kamran Ashraf
- 2. Formal Problem Definition •Given a sequence of numbers <a1,a2,…..an> we work to find a subsequence of A that is contiguous and whose values have the maximum sum. • Maximum Subarray problem is only challenging when having both positive and negative numbers.
- 3. Example… Here, the subarrayA[8…11] is the Maximum Subarray, with sum 43, has the greatest sum of any contiguous subarray of array A.
- 4. Brute Force Solution Tosolve the Maximum Subarray Problem we can use brute force solution however in brute force we will have to compare all possible continuous subarray which will increase running time. Brute force will result in Ѳ(n2), and the best we can hope for is to evaluate each pair in constant time which will result in Ὠ(n2). Divide and Conquer is a more efficient method for solving large number of problems resulting in Ѳ(nlogn).
- 5. Divide and ConquerSolution • First we Divide the array A [low … high] into two subarrays A [low … mid] (left) and A [mid +1 … high] (right). • We recursively find the maximum subarray of A [low … mid] (left), and the maximum of A [mid +1 … high] (right). • We also find maximum crossing subarray that crosses the midpoint. • Finally we take a subarray with the largest sum out of three.
- 6.
- 7. Time Analysis • Find-Max-Cross-Subarraytakes: Ѳ (n) time • Two recursive calls on input size n/2 takes: 2T(n/2) time • Hence: T(n) = 2T(n/2) + Ѳ (n) T(n) = Ѳ (n log n)
- 8. Pseudo Code Max-subarray(A, Left,Right) if (Right == Left) return (left, right, A[left]) else mid= [(left+right)/2] L1=Find-Maximum-Subarray(A,left,mid) R1=Find-Maximum-Subarray(A,mid+1,right) M1=Find-Max-Crossing-Subarray(A,left,mid,right) If sum(L1) > sum(R1) and sum(L1) > sum(M1) Return L1 elseif sum(R1) > sum(L1) and sum(R1) > sum(M1) Return R1 Else return M1