title: find the lowest absolute sum of elements from an array
body: <p>I try to understand a solution from a problem in the Codility provided below,</p>
  
  <p>For a given array A of N integers and a sequence S of N integers from the set {−1, 1}, we define val(A, S) as follows:</p>
  
  <pre><code>val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }|
  </code></pre>
  
  <p>(Assume that the sum of zero elements equals zero.)</p>
  
  <p>For a given array A, we are looking for such a sequence S that minimizes val(A,S).</p>
  
  <p>Write a function:</p>
  
  <pre><code>class Solution { public int solution(int[] A); }
  </code></pre>
  
  <p>that, given an array A of N integers, computes the minimum value of val(A,S) from all possible values of val(A,S) for all possible sequences S of N integers from the set {−1, 1}.</p>
  
  <p>For example, given array:</p>
  
  <pre><code>  A[0] =  1
    A[1] =  5
    A[2] =  2
    A[3] = -2
  </code></pre>
  
  <p>your function should return 0, since for S = [−1, 1, −1, 1], val(A, S) = 0, which is the minimum possible value.</p>
  
  <p>Assume that:</p>
  
  <pre><code>N is an integer within the range [0..20,000];
  each element of array A is an integer within the range [−100..100].
  Complexity:
  </code></pre>
  
  <p>expected worst-case time complexity is O(N*max(abs(A))2);
  expected worst-case space complexity is O(N+sum(abs(A))) (not counting the storage required for input arguments).</p>
  
  <p>I have the solution that I'm trying to understand for the last few hours. </p>
  
  <pre><code>public static int solution(int[] A) {
  
          int N = A.length;
  
          int sum = 0;
          int max = 0;
  
          for (int i = 0; i &lt; N; i++) {
  
              A[i] = Math.abs(A[i]);
              sum += A[i];
  
              max = Math.max(A[i], max);
          }
  
  
          int[] counts = new int[max + 1];
  
          for (int i = 0; i &lt; N; i++) {
              counts[A[i]] += 1;
          }
  
          int[] Total = new int[sum + 1];
  
          Arrays.fill(Total, -1);
          Total[0] = 0;
  
          // Segment I
          for (int i = 1; i &lt;= max; i++) {
  
              if (counts[i] &gt; 0) {
  
                  for (int j = 0; j &lt;= sum; j++) {
  
                      // j th index is zero or positive
                      if (Total[j] &gt;= 0) {
                          Total[j] = counts[i];
                      }
                      // (i-j) th index is positive
                      else if ((j - i) &gt;= 0 &amp;&amp; Total[j - i] &gt; 0) {
                          Total[j] = Total[j - i] - 1;
                      }
                  }
              }
          }
  
          int result = sum;
  
          // Segment II
          for (int i = 0; i &lt; sum / 2 + 1; i++) {
  
              // i- th index if zero or positive
              // BODMAS_RULE = {Brackets, Orders, Division, Multiplication, Addition, Subtraction}
              if (Total[i] &gt;= 0) {
                  result = Math.min(result, sum - 2 * i);
              }
          }
  
          return result;
      }
  </code></pre>
  
  <p>If anyone can explain whats going on in the last 2 segments of the loops, it will be very helpful.  All I look for a brief explanation within few lines of text.</p>
  
  <h2>UPADTE</h2>
  
  <p>I would like to understand why do we use conditions in the for loop of the first segment. Besides, why do we iterate till the <code>sum / 2 + 1</code> in the second for loop. Thank you.    </p>