0

给定一个正数数组，您需要找到两个不相交的子序列，其最小差小于或等于 n。这些子序列可能是连续的，也可能不是连续的

For Example 

if array = [10,12,101,105,1000] and n = 10
Ans = [10,105] & [12,101]

If minimum difference > n then there is no solution.

Ex- array = [100, 150, 125] and n = 7

我认为这可以使用 DP 来完成，但我无法得出递归。

4

1 回答 1

0

如果你所有元素的总和不是太大（数百万以内），那么你可以做一个类似于背包问题的解决方案。您的 DP 状态是两个集合之间的差异，并且对于每个元素，您都迭代了迄今为止您知道的所有差异，并更新它们。由于差异不能超过所有元素的总和，因此复杂性最终O(n * s)是n元素的数量和s它们的总和。您将需要某种逻辑来恢复答案。例如，如果你所有的元素都是非负的，你可以只存储之前的差异。这是一个示例 python 代码（我稍微修改了您的示例案例，因为对于您的案例，它找到了一个不感兴趣的答案[10], [12]）

a = [5, 20, 30, 1000]
n = 7

states = {(0, False, False): None} # state is sum, hasPositive, hasNegative => prevsum, prevHasP, prevHasN
for el in a:
    newStates = {}

    for k, v in states.items():
        newStates[k] = v

    for v, hasP, hasN in states:
        if (v + el, True, hasN) not in newStates:
            newStates[(v + el, True, hasN)] = (v, hasP, hasN)
        if (v - el, hasP, True) not in newStates:
            newStates[(v - el, hasP, True)] = (v, hasP, hasN)

    states = newStates

best = None
for key, hasP, hasN in states.keys():
    if key >= -n and key <= n and hasP and hasN and (best == None or abs(best[0]) > abs(key)):
        best = (key, hasP, hasN)

if best is None: print "Impossible"
else:
    ans1 = []
    ans2 = []
    while best[1] or best[2]: # while hasPositive or hasNegative
        prev = states[best]

        delta = best[0] - prev[0]
        if delta > 0:
            ans1.append(delta)
        else:
            ans2.append(- delta)

        best = prev

    print ans1
    print ans2

正如我之前提到的，它只有在你的所有元素都是非负数时才有效，但是如果元素可以是负数，很容易调整恢复答案的代码也可以工作。

于 2015-02-11T06:39:58.353 回答