Given an array of positive and unique integers, I am trying to write an algorithm which returns an increasing subsequence that:

(1) has length within given bounds L and H, L <= length <= H, and

(2) has the maximum sum

I know that I should be using dynamic programming for this and I have an understanding how I would solve a similar problem to find a subsequence with maximum sum but unsure how to fit in the constraint of the subsequence min and max length. What is the algorithm or pseudocode for how I can solve this using dynamic programming?

CodePudding user response：

Seems two-pointers approach should work here

Set left and right indices into 0

Move right index while A[right 1]>A[right] and right-left < H

If you meet decrease, jump left index into the right position and start moving right again.

If length reaches H-L, start move left pointer together with right one (note left..right range is always sorted)

CodePudding user response：

I would iterate the positions i of the array, and define s[i] as the sum of up to H increasing elements e[i] < e[i 1] < ... if there are at least L such elements, and 0 otherwise. Then you only need to maximize s[i].