# Select optimal subintervals from array

I have an input array and I have to select an indefinite number of intervals from it so that the "profit" is maximal and I have exactly T elements selected in total, where T is given. Profit means the sum of all the elements of an interval, except for the first element. An interval can consist of a single element, meaning that the profit for such an interval is 0. The array may contain negative numbers. Apparently dynamic programming is the answer to this problem, but I cannot think of an efficient algorithm to solve it. This is homework, so I would appreciate any help.

• The new formulation is even simpler: Take the $T$ maximal elements of your array (leaving out the first one), and the one just before each contiguous range thus created. Mar 11 '13 at 1:16