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...

  • $\begingroup$ Sorry @vonbrand I misunderstood my task. I have updated the question. $\endgroup$ – Johnny Mar 10 '13 at 22:06
  • $\begingroup$ 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. $\endgroup$ – vonbrand Mar 11 '13 at 1:16
  • $\begingroup$ For example, for the array [2000(pos 100) 1995(pos 101) 1999(pos 105) 1994(pos 106) 1998(pos 110) 1997(pos 115) 1996(pos 120)] if I want to extract 10 elements so that the profit is maximal, the optimal solution is [x 2000 1995] [y 1999 1994] [z 1998] [t 1997]. By using your advice, I would be selecting the largest five elements of the array and an extra element before each of them. $\endgroup$ – Johnny Mar 11 '13 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.