2

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

它看起来像一个DP问题。

  • LetS1[i]是一个子序列a[i]，其总和> 0且abs（总和）最小化。

  • LetS2[i]是一个子序列，在该子序列处a[i]其总和 < 0 并且abs (sum) 被最小化。

  • S1[i]是if > 0 && < 0S1[j] + a[i]的最小值j < iS1[j] + a[i]a[i]

  • S2[i]是if < 0 && > 0S2[j] + a[i]的最小值j < iS2[j] + a[i]a[i]

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

是否有意义？

4

3 回答 3

2

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

由于元素的顺序无关紧要，您的问题只是问：给定一组（多）元素，所有子集之间的最小绝对和是多少。很容易看出，子集和问题简化为这个问题。由于子集和是 NP 难的，所以这个问题也是如此。因此，很可能您的多项式时间算法是错误的。否则，P = NP。

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

子集和问题的标准方法可用于为您的问题获取伪多项式时间算法。

于 2013-03-11T17:04:37.803 回答
1

我希望我能按照你的推理，但我有点慢......你还要求DP，这里又是Haskell......但这是你的意思吗？

import Data.List (sortBy, subsequences)
import Data.Ord (comparing)

minValSub xs = 
  head $ sortBy (comparing snd) 
  $ map (\x -> (x, abs (sum x)) ) (filter (not . null) $ subsequences xs)


OUTPUT:
*Main> minValSub [1,2,3,-4,5]
([1,3,-4],0)
于 2013-03-11T18:35:51.017 回答
1

我假设非空结果集。

设整数列表为 S。考虑其中最小的绝对值S[k]。如果 S[K] == 0 则返回它。否则目标是找到一个小于 S[K] 的值。

如您提到的SP（非负）和SN，将整数分为两组正整数和负整数。现在找到 SP 中的总和，它与 SN 中的另一个总和小于 S[K]。这可以通过按绝对值分别对 SP 和 SN 中的元素进行排序，在每个列表上保留一个总和和一个头指针来完成。您可以填写详细信息。

这可能给出小于 S[K] 的值，否则报告 S[K]。

例如：S = {1, -4, 2, -8, 5, -7} k = 0, S[k] = 1

SP（排序）= {1, 2, 5} SN（排序）= {-4, -7, -8}

同时遍历这两个数组，你可以得到一些候选 {1,2} 和 {-4}，它们将给出与 S[k] 相同的结果。但是 {2,5} 和 {-7} 会更好地给出 0 的净总和。

于 2013-03-11T21:16:23.717 回答