title: MaxDoubleSliceSum Algorithm
body: <p>I'm trying to solve the problem of finding the MaxDoubleSliceSum value. Simply, it's the maximum sum of any slice minus one element within this slice (you have to drop one element, and the first and the last element are excluded also). So, technically the first and the last element of the array cannot be included in any slice sum.</p>
  
  <p>Here's the full description:</p>
  
  <p>A non-empty zero-indexed array <code>A</code> consisting of <code>N</code> integers is given.
  A triplet <code>(X, Y, Z)</code>, such that <code>0 ≤ X &lt; Y &lt; Z &lt; N</code>, is called a double slice.
  The sum of double slice <code>(X, Y, Z)</code> is the total of <code>A[X + 1] + A[X + 2] + ... + A[Y − 1] + A[Y + 1] + A[Y + 2] + ... + A[Z − 1]</code>.</p>
  
  <p>For example, array <code>A</code> such that:</p>
  
  <pre><code>A[0] = 3
  A[1] = 2
  A[2] = 6
  A[3] = -1
  A[4] = 4
  A[5] = 5
  A[6] = -1
  A[7] = 2
  </code></pre>
  
  <p>contains the following example double slices:</p>
  
  <p>double slice <code>(0, 3, 6)</code>, sum is <code>2 + 6 + 4 + 5 = 17</code>,</p>
  
  <p>double slice <code>(0, 3, 7)</code>, sum is <code>2 + 6 + 4 + 5 − 1 = 16</code>,</p>
  
  <p>double slice <code>(3, 4, 5)</code>, sum is <code>0</code>.</p>
  
  <p>The goal is to find the maximal sum of any double slice.</p>
  
  <p>Write a function:</p>
  
  <p><code>def solution(A)</code>
  that, given a non-empty zero-indexed array <code>A</code> consisting of <code>N</code> integers, returns the maximal sum of any double slice.</p>
  
  <p>For example, given:</p>
  
  <pre><code>A[0] = 3
  A[1] = 2
  A[2] = 6
  A[3] = -1
  A[4] = 4
  A[5] = 5
  A[6] = -1
  A[7] = 2
  </code></pre>
  
  <p>the function should return <code>17</code>, because no double slice of array <code>A</code> has a sum of greater than <code>17</code>.</p>
  
  <p>Assume that:</p>
  
  <p><code>N</code> is an integer within the range [3..100,000];</p>
  
  <p>each element of array <code>A</code> is an integer within the range <code>[−10,000..10,000]</code>.</p>
  
  <p>Complexity:</p>
  
  <p>expected worst-case time complexity is <code>O(N)</code>;</p>
  
  <p>expected worst-case space complexity is <code>O(N)</code>, beyond input storage (not counting the storage required for input arguments).</p>
  
  <p>Elements of input arrays can be modified.</p>
  
  <p>Here's my try:</p>
  
  <pre><code>def solution(A):
      if len(A) &lt;= 3:
          return 0
      max_slice = 0
      minimum = A[1]    # assume the first element is the minimum
      max_end = -A[1]   # and drop it from the slice
      for i in xrange(1, len(A)-1):
          if A[i] &lt; minimum:        # a new minimum found
              max_end += minimum    # put back the false minimum
              minimum = A[i]        # assign the new minimum to minimum
              max_end -= minimum    # drop the new minimum out of the slice
          max_end = max(0, max_end + A[i])
          max_slice = max(max_slice, max_end)
      return max_slice
  </code></pre>
  
  <p>What makes me think that this may approach the correct solution but some corners of the problem may haven't been covered is that 9 out 14 test cases pass correctly (<a href="https://codility.com/demo/results/demoAW7WPN-PCV/" rel="nofollow">https://codility.com/demo/results/demoAW7WPN-PCV/</a>)
  I know that this can be solved by applying Kadane’s algorithm forward and backward. but I'd really appreciate it if someone can point out what's missing here.</p>