The problem is the following. Suppose we have a sequence of
n non-negative numbers, each element with index
i having its own value,
We want to put some cells in a subsequence
Plus, and some cells in the subsequence
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
Plus with the same indexes in the respective sequences), that might have non-selected elements between them, in the starting sequence. The
Minus subsequences have to be of the same length, but that length must be at most a given value
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:
Recursive(i,prev_selection,remaining_selections): 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
Can you suggest some algorithm with better complexity? I feel like I am missing some property of the problem that can speed things up.