The max subarray problem requires finding pairs of indices $i$ and $j$ that maximize some objective function for an array. For example, given a list of stock prices over time, find the time $i$ to buy and time $j$ to sell that would result in the largest gain for the period. An efficient solution utilizes [[divide-and-conquer]] to split the array recursively and find the solution in each base case. When combining, the solution may be 1. contained in the left subarray 2. contained in the right subarray or 3. straddle the two subarrays. To determine if the solution is in fact in this third case, calculate the difference between the minimum element in the left and maximum element in the right. Then simply select the maximum from the three cases in each combination step. In pseudocode, to find the max subarray given an array `A`, a lower index `l` and an upper index `u`: ``` maxSubarray(A, l, u): # base cases if u == l: # list is one element return 0 if u == l + 1 # list is two elements return max(A[u] - A[l], 0) # recursively call maxSubarray by spliting at midpoint element midpoint = (l + u) // 2 maxLower = maxSubarray(A, l, m) maxUpper = maxSubarrya(A, m+1, u) # check straddle case straddleL = getMinElement(A, l, m) straddleU = getMaxElement(A, m+1, u) # combine and return return max(maxLower, maxUpper, straddleU - straddleL) ``` The pseudocode requires the helper functions `getMaxElement` and `getMinElement` which simply gets the `max` and `min` from a subarray in linear time. The runtime of this algorithm is $\Theta(n \lg n)$.