title: Subsequence with minimal absolute value
body: <p>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.</p>
  
  <p>It looks like a DP problem. </p>
  
  <ul>
  <li><p>Let <code>S1[i]</code> is a subsequence ending at <code>a[i]</code> for which its sum > 0 and <em>abs</em>(sum) is minimized. </p></li>
  <li><p>Let <code>S2[i]</code> is a subsequence ending at <code>a[i]</code> for which its sum &lt; 0  and <em>abs</em>(sum) is minimized.</p></li>
  <li><p><code>S1[i]</code> is the minimum of all <code>S1[j] + a[i]</code> for <code>j &lt; i</code> if <code>S1[j] + a[i]</code> > 0 &amp;&amp;  <code>a[i]</code> &lt; 0</p></li>
  <li><p><code>S2[i]</code> is the minimum of all <code>S2[j] + a[i]</code> for <code>j &lt; i</code> if <code>S2[j] + a[i]</code> &lt; 0 &amp;&amp;  <code>a[i]</code> > 0</p></li>
  </ul>
  
  <p>Once we now <code>S1[i]</code> and <code>S2[i]</code> for all indexes it is easy to find the subsequence with the mininimal absolute value of its elements.</p>
  
  <p>Does it make sense?  </p>