I'm reading Introduction to Algorithms 3rd edition by clrs, and on page 69(Maximum subarray problem) in the paragraph..."A transformation",it's stated that n-1 choose 2 = Theta (n^2) subarrays are still needed to check.I don't understand that,as we already found the maximum subarray,then why do we need to further check subarrays and that too.. why from n-1 choose 2?we are choosing subsequences...not two days...!
I check the book, and found that maybe you don't really get the point of the question, the question can be transformed to the famous subarray problem.
The subarray problem is given an array, find the the subarray which has the maximun sum of all its element.
So, the brute force algorithm in the books means that, you can check all start point and end point of the subarray, which is n-1 choose 2, because we have n-1 elements in the array, and we can choose any of two to be begin and end, so the complexity is O(n^2), hope this help you!
reference: Introduction to algorithms 3rd edition