Longest increasing subsequence with maximum sum with allowed number of elements to be skipped

  • 1

    The longest increasing subsequence with maximum sum (http://www.geeksforgeeks.org/dynamic-programming-set-14-maximum-sum-increasing-subsequence/) is a classic algorithm problem and there exist a lot of solutions on the web. However, I just encountered a variation of this problem and have no idea how to solve it.
    Compared with the original question, now you are also given a number m which indicates the number of elements you can skip at most from a continuous sub-range in order to find the LIS with maximum sum. For example, with the following array,

    1,200,300, 4, 100, 50, 5, 6, 7, 8

    The LIS is 1,4,5,6,7,8 if there is no constraint. However, if m is 1, it means that only one element can be skipped in a continuous sub-range in order to find the LIS. Hence the above solution is not right and the new solution should be 5,6,7,8 since no elements are skipped in a continuous sub-range. If m is 2, then the answer will be 4,5,6,7,8. If m is 3, the answer remains the same and if m is 4, the answer becomes 1,4,5,6,7,8.

    The question is to find the LIS with the maximum sum and return the subsequence (not the sum or the length of the subsequence) when the array and the number m is given. I have been stuck with this problem for several days so any help is appreciated.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.