The brute force solution that seems most obvious to me is to pick a starting index and an ending index out of all possible indexes such that start < end, and ca

The brute force solution that seems most obvious to me is to pick a starting index and an ending index out of all possible indexes such that start < end, and calculate the sum of that sub-array (keeping the biggest result). This is O(N^3) because iterating over index pairs is O(N^2) and doing the sum is O(N).