title: Most efficient way to sum up an array of integers
body: <p>I am trying to find a sub-<code>O(n)</code> method to calculate the sum of an integer array ~~~(instead of iterating through <code>0 - n</code>, I am doing it in <code>n/2</code>)~~~ <strong>I'm still doing it in O(n)</strong>.</p>
  
  <pre><code>public static int sum(int[] s) {
      int length = s.length - 1;
      int half = length/2;
      int sum = 0;
      for(int i = 0; i &lt;= half; i++) {
          System.out.println(i + " " + s[i] + " + " + s[length - i]);
          sum += s[i] + s[length - i];
      }
      return sum;
  }
  </code></pre>
  
  <p>My algorithm works for even number of integers, however, when there are odd number of integers, it would sum the middle index twice:</p>
  
  <p>Test:</p>
  
  <pre><code>    int[] arr = {1, 2, 3, 4, 5};
      System.out.println(sum(arr));
  </code></pre>
  
  <p>Output:</p>
  
  <pre><code>0 1 + 5
  1 2 + 4
  2 3 + 3
  Sum: 18
  </code></pre>
  
  <p>My question is - what is the best way to sum up the middle index for odd-number of numbers?</p>