Geek asks and answers

Subsequence with minimum absolute value

This is an interview question. For an integer array, find a subsequence (not necessarily continuous) for which the absolute value of the sum of its elements is minimized.

This seems like a DP problem.

  • Let be S1[i]a subsequence ending in a[i]for which its sum> 0 and abs (sum) are minimized.

  • Let be S2[i]a subsequence ending in a[i]for which its sum <0 and abs (sum) are minimized.

  • S1[i]is the minimum for all S1[j] + a[i]for j < i, if S1[j] + a[i]> 0 && <t21 <0

  • S2[i]is the minimum of all S2[j] + a[i]for j < iif S2[j] + a[i]<0 && a[i]> 0

As soon as we are now S1[i]and S2[i]for all indices, it is easy to find a subsequence with a minimum absolute value of its elements.

Does it make sense?

+2
source share
3 answers

I assume that you need a minimum absolute sum among non-empty subsequences. (Otherwise, as indicated in the comments, the empty subsequence has a sum of 0.)

, : () , . , . NP-, . , . P = NP.

, {-1, 2, -2}.

.

+2

, , ... 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)
+1

.

S. absolute 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.

+1

More articles:


All Articles