Time Limit: 3s
Memory Limit: 128MB
The maximum subarray problem is the task of finding within a sequence of numbers a contiguous subarray which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
* In general, there may be multiple maximum subarrays (i.e. a tie). However, our test cases will not have any ties.
line 0: size of array n
line 1~n: array elements, one element per line
line 0: low index of the maximum subarray
line 1: high index of the maximum subarray
line 2: sum of the maximum subarray
5 3 -1 6 -5 -10
0 2 8