The Maximum Subarray Problem

1. The Maximum Subarray Problem 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 subarray A[8…11 ] is the Maximum Subarray , with sum 43, has the greatest sum of any contiguous subarray of array A.

4. Brute Force Solution To solve 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 Ѳ(n 2 ), and the best we can hope for is to evaluate each pair in constant time which will result in Ὠ(n 2 ). Divide and Conquer is a more efficient method for solving large number of problems resulting in Ѳ( nlogn ) .

5. 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 .

6. Example…

7. Time Analysis Find-Max-Cross- Subarray takes: Ѳ (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