title: Reaching the end of an array with a sequence of odd/even jumps
body: <p>I'm trying to understand a Python solution to a programming puzzle that seems to use dynamic programming. I am able to follow most of the solution, but I'm struggling a bit to really formalize the solution.</p>
  
  <p>The problem is stated as follows:</p>
  
  <blockquote>
    <p>You are given an integer array <code>A</code>.  From some starting index, you can
    make a series of jumps.  The (1st, 3rd, 5th, ...) jumps in the series
    are called "odd" numbered jumps, and the (2nd, 4th, 6th, ...) jumps in
    the series are called even numbered jumps. </p>
    
    <p>You may jump <strong>forward</strong> from index <code>i</code> to index j (with <code>i &lt; j</code>) in the following way: </p>
    
    <ul>
    <li><p>During <strong>odd</strong> numbered jumps (ie. jumps 1, 3, 5, ...), you jump to the index <code>j</code> such
    that <code>A[i] &lt;= A[j]</code> and <code>A[j]</code> is the <strong>smallest</strong> possible value.  If there
    are multiple such indexes <code>j</code>, you can only jump to the smallest such
    index j. </p></li>
    <li><p>During <strong>even</strong> numbered jumps (ie. jumps 2, 4, 6, ...), you jump
    to the index <code>j</code> such that <code>A[i] &gt;= A[j]</code> and <code>A[j]</code> is the <strong>largest</strong> possible
    value.  If there are multiple such indexes <code>j</code>, you can only jump to the
    <strong>smallest</strong> such index <code>j</code>.</p></li>
    <li><p>It may be the case that for some index <code>i</code> are <strong>no legal</strong> jumps.</p></li>
    </ul>
    
    <p>A starting index is <strong>good</strong> if, starting from that index, you can reach the end of the array by jumping some number of times (possibly 0 or more than once.) </p>
    
    <p>We ask that you return the number of <strong>good starting</strong> indices.</p>
  </blockquote>
  
  <p>Below I show a solution in Python to this problem that a few authors have published.  I understand how it builds <code>oddnext</code> and <code>evennext</code> and what these arrays technically hold (the index location one jumps to from that index with an odd or even jump). What I don't understand is how the last loop works, and what's the precise dynamic programming formulation behind it.</p>
  
  <pre><code>def odd_even_jumps(self, A):
      N = len(A)
  
      def make(B):
          ans = [None] * N
          stack = []  # invariant: stack is decreasing
          for i in B:
              while stack and i &gt; stack[-1]:
                  ans[stack.pop()] = i
              stack.append(i)
          return ans
  
      B = sorted(range(N), key = lambda i: A[i])
      oddnext = make(B)
      B.sort(key = lambda i: -A[i])
      evennext = make(B)
  
      odd = [False] * N
      even = [False] * N
      odd[N-1] = even[N-1] = True
  
      # Why does this loop start from the end? 
  
      for i in range(N-2, -1, -1):
          if oddnext[i] is not None:
              odd[i] = even[oddnext[i]]
          if evennext[i] is not None:
              even[i] = odd[evennext[i]]
  
      return sum(odd)
  </code></pre>