找到两个具有最小差异（> n）的不相交的序列

Question

给你一个正数数组，你需要找到两个不相交的子序列，它们的最小差值小于或等于 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 来完成，但我无法得出重复。

Answer 1

如果你所有元素的总和不是太大（百万以内），那么你可以做一个类似背包问题的解法。您的 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

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

找到两个具有最小差异（> n）的不相交的序列

Find two disjoint susequences with minimum difference( > n)

algorithm

dynamic-programming

combinatorics

subsequence