## Solution - Find the prefix sum. scan for mins and maxes, and find the maximum min-max pair (max must come after min, can be done with one scan). ## Problem ### Problem Description Given an integer array $\texttt{nums}$, find the subarray with the largest sum, and return its sum. #### Example 1 - **Input:** $\texttt{nums} = [-2, 1, -3, 4, -1, 2, 1, -5, 4]$ - **Output:** $6$ - **Explanation:** The subarray $[4, -1, 2, 1]$ has the largest sum $6$. #### Example 2 - **Input:** $\texttt{nums} = [1]$ - **Output:** $1$ - **Explanation:** The subarray $[1]$ has the largest sum $1$. #### Example 3 - **Input:** $\texttt{nums} = [5, 4, -1, 7, 8]$ - **Output:** $23$ - **Explanation:** The subarray $[5, 4, -1, 7, 8]$ has the largest sum $23$. ### Constraints - $1 \leq \texttt{nums.length} \leq 10^5$ - $-10^4 \leq \texttt{nums}[i] \leq 10^4$ ### Follow Up If you have figured out the $O(n)$ solution, try coding another solution using the divide and conquer approach, which is more subtle.