子序列与最小绝对值 [英] Subsequence with minimal absolute value
问题描述
这是一个面试问题。给定一个整数数组找到的亚序列（不必是连续）的量其元素的总和的绝对值最小化。
This is an interview question. Given an integer array find a subsequence (not necessarily contiguous) for which the absolute value of the sum of its elements is minimized.
它看起来像一个DP的问题。
It looks like a DP problem.
-
让
S1 [I]是一个子序列在结尾的[I]为此其总和> 0和绝的（和）被最小化。
Let
S1[i]is a subsequence ending ata[i]for which its sum > 0 and abs(sum) is minimized.
让 S2 [I] 是一个子序列在结尾的[I] 为此其总和＆LT; 0和 ABS 的（和）最小化。
Let S2[i] is a subsequence ending at a[i] for which its sum < 0 and abs(sum) is minimized.
S1 [I] 是最小的是 S1 [J] + A [1] 为 J＆LT;我如果 S1 [J] + A [1] > 0安培;＆安培; A [1] ＆LT; 0
S1[i] is the minimum of all S1[j] + a[i] for j < i if S1[j] + a[i] > 0 && a[i] < 0
S2 [I] 是最小的是 S2 [J] + A [1] 为 J＆LT;我如果 S2 [J] + A [1] ＆LT; 0安培;＆安培; A [1] > 0
S2[i] is the minimum of all S2[j] + a[i] for j < i if S2[j] + a[i] < 0 && a[i] > 0
在我们现在 S1 [I] 和 S2 [I] 所有索引很容易找到与子元素的mininimal绝对值。
Once we now S1[i] and S2[i] for all indexes it is easy to find the subsequence with the mininimal absolute value of its elements.
是否有意义？
推荐答案
我假设你想在非空的子序列的最小绝对值和。 （否则中提到的意见，空子序列之和0。）
I'm assuming you want the minimum absolute sum among non-empty subsequences. (Otherwise as mentioned in the comments, the empty subsequence has sum 0.)
由于元素的顺序并不重要，你的问题只是要求：给定一个（多）集合中的元素，什么是所有子集之间的最小绝对值之和。这是很容易看到，子集和问题的降低这一问题。由于子集之和为NP-辛苦，所以这方面的问题。因此，这是一个不错的选择，你的多项式时间的算法是错误的。否则，P = NP。
Since the order of the elements doesn't matter, your question just asks: given a (multi)set of elements, what is the minimum absolute sum among all subsets. It is easy to see that the subset sum problem reduces to this problem. Since subset sum is NP-hard so is this problem. Therefore, it is a good bet that your polynomial time algorithm is wrong. Otherwise, P = NP.
在实际上，一个反向你的算法是输入序列{-1，2，-2}
In fact, a counterexample to your algorithm is the input sequence {-1, 2, -2}.
<一个href="http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution"相对=nofollow>标准方法添加到子集和问题可以用于获得伪多项式时间算法您的问题。
Standard approaches to the subset sum problem can be used to obtain pseudo-polynomial time algorithms for your problem.
这篇关于子序列与最小绝对值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
