The problem is the following. Suppose we have a sequence of n non-negative numbers, each element with index i having its own value, value[i].
We want to put some cells in a subsequence Plus, and some cells in the subsequence Minus.

Not all the elements have to be in one of these subsequences, one might not be in any one of them, but the two subsequences are exclusive.

Of course, the elements of each subsequence must have the same relative order in the subsequences as they had in the starting sequence.

The element with the lowest index in the starting sequence that is included in some subsequence (not necessarily the first one, as we can leave arbitrarily many elements unselected - not included in any subsequence - between two selections), has to be part of the Minus subsequence - that is, the first element of the Minus sequence must have a lower index than the first element of the Plus sequence in the starting sequence.

When an element of the starting sequence is put in the Plus subsequence, the element with the immediately higher index that will be selected (not necessarily the next one, we might leave some elements unselected as described above) HAS to be put in Minus, and vice versa - that is, no two selected elements might be in the same subsequence, if there is no other selected element between them in the original sequence belonging to the other subsequence, so in essence the elements of the two subsequences form "pairs" (two elements of the Minus and Plus with the same indexes in the respective sequences), that might have non-selected elements between them, in the starting sequence. The Plus and Minus subsequences have to be of the same length, but that length must be at most a given value K.

Given that V = sum(Plus) - sum(Minus), I want to find out what is the maximum V possible, given the starting sequence.

V can also be 0, if, for example, the contents of the starting sequence are larger the larger the index.

What I have come up with so far, is a dynamic programming algorithm with memoisation, having a n*2*K array to store the computed results, and eventually computing as many calls of the Recursive function to get the final result. The pseudocode is as follows:

    if remaining_selections<=0 or i>n:
        return 0

    if computed[i,prev_selection,remaining_selections] != EMPTY:
        return computed[i,prev_selection,remaining_selections]  

    if previous_selection  == Plus:  

        GoesToMinus = Recursive(i+1,Minus,remaining_selections) - value[i]   

        IsNotSelected = Recursive(i+1,Plus,remaining_selections)   

        computed[i,prev_selection,remaining_selections] = max(GoesToMinus,IsNotSelected)  

        return computed[i,prev_selection,remaining_selections]  

    else if previous_selection == Minus:  

        GoesToPlus = Recursive(i+1,Plus,remaining_selections-1) + value[i]
        //Selections are only decreased when selecting a Plus
        //Remember that Minus is always selected first   

        IsNotSelected = Recursive(i+1,Minus,remaining_selections)  

        computed[i,prev_selection,remaining_selections] =  max(GoesToPlus,IsNotSelected)    

        return computed[i,prev_selection,remaining_selections]

The result is found by executing Recursive(1,Plus,K). The space as well as the time complexity in this is Θ(n*K).

Can you suggest some algorithm with better complexity? I feel like I am missing some property of the problem that can speed things up.


Your Answer

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

Browse other questions tagged or ask your own question.