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.
Search for maximum subsequence sum problem, here you will find a linear time solution. Bentley's "Programming Pearls" gives several alternative algorithms and some history. The linear time solution is obvious in hindsight, but it took several tries by experts to come up with it...