If thinking about reducing the duplicate steps, then this traditional method of
pre-computing the sum-array is a dp solution, because it use the cumulative sum
as a memorization table. The time complexity is O(n^2) here.
Another method is to use divide & conquer, which can result in O(n log n) run time. But I do not want to code it out after seeing the solution there.