arrays - 绝对值最小的子序列

Question

这是一道面试题。给定一个整数数组，找到一个子序列(不一定是连续的)，其元素之和的绝对值最小。

看起来像是DP问题。

• 让 S1[i]是一个以 a[i] 结尾的子序列它的总和 > 0 和 abs(sum) 被最小化。

• 让 S2[i]是一个以 a[i] 结尾的子序列其总和 < 0 和 abs(sum) 最小化。

• S1[i]是所有 S1[j] + a[i] 中的最小值对于 j < i如果S1[j] + a[i] > 0 && a[i] < 0

• S2[i]是所有 S2[j] + a[i] 中的最小值对于 j < i如果S2[j] + a[i] < 0 && a[i] > 0

一旦我们现在S1[i]和 S2[i]对于所有索引，很容易找到其元素绝对值最小的子序列。

有意义吗？

Answer 1

我假设您想要非空子序列中的最小绝对和。 (否则如评论中所述，空子序列的总和为 0。)

由于元素的顺序无关紧要，您的问题只是问:给定一组(多)元素，所有子集的最小绝对总和是多少。很容易看出 subset sum problem减少到这个问题。由于子集和是 NP-hard，所以这个问题也是如此。因此，很可能您的多项式时间算法是错误的。否则，P = NP。

事实上，您的算法的一个反例是输入序列 {-1, 2, -2}。

Standard approaches对子集和问题的求解可用于为您的问题获取伪多项式时间算法。