1. **Problem Statement:** We want to find a contiguous subarray of length $\log n$ in an array of $n$ numbers (where $n$ is a power of 2) that has the maximum sum. 2. **Naive Approach:** Check all subarrays of length $\log n$. There are $n - \log n + 1$ such subarrays, and summing each takes $O(\log n)$ time, resulting in $\Theta(n \log n)$ time complexity. 3. **Divide-and-Conquer Strategy:** - Divide the array into two halves of length $n/2$ each. - Recursively find the maximum sum subarray of length $\log n$ in each half. - Consider subarrays of length $\log n$ that cross the midpoint. 4. **Key Insight for Crossing Subarray:** - Since $\log n = \log(n/2) + 1$, the crossing subarray must include elements from both halves. - We split the $\log n$ length into $k$ elements from the left half and $\log n - k$ from the right half for $k=1$ to $\log n - 1$. - For each $k$, find the maximum suffix sum of length $k$ in the left half and maximum prefix sum of length $\log n - k$ in the right half, and sum them. 5. **Efficient Computation of Crossing Sums:** - Precompute prefix sums and suffix sums for all possible subarray lengths up to $\log n$ within each half in $O(n)$ time. - Combine these in $O(\log n)$ time for all $k$. 6. **Recurrence Relation:** $$T(n) = 2T \left(\frac{n}{2}\right) + O(\log n)$$ 7. **Solving the Recurrence:** - Use the Master Theorem or recursion tree: $$\begin{aligned} T(n) &= 2T\left(\frac{n}{2}\right) + c \log n \\ &= 2\left[2T\left(\frac{n}{4}\right) + c\log\frac{n}{2}\right] + c\log n \\ &= 4T\left(\frac{n}{4}\right) + 2c\log\frac{n}{2} + c\log n \\ &= \dots \\ &= nT(1) + c\sum_{i=0}^{\log n - 1} 2^i \log\left(\frac{n}{2^i}\right). \end{aligned}$$ - Simplify the sum: $$\sum_{i=0}^{\log n - 1} 2^i (\log n - i) = \log n \sum_{i=0}^{\log n - 1} 2^i - \sum_{i=0}^{\log n - 1} i 2^i.$$ - Both sums grow asymptotically like $n \log n$ and $n$. - Thus, the overall complexity is: $$T(n) = O(n) + O(n \log \log n) = O(n \log \log n).$$ 8. **Conclusion:** Using divide-and-conquer and precomputing prefix/suffix sums, the algorithm finds the maximum sum subarray of length $\log n$ in $O(n \log \log n)$ time, which is faster than the brute-force $\Theta(n \log n)$ approach.