jump.py

class Solution(object):
    def solution(self, A):
        n = len(A)
        res = [n-1]                # last element is counted
        even = {n-1: True, None: False}
        odd = {n-1: True, None: False}

        def check_pos(i, flag):
            if flag % 2:
                if i in odd:
                    return odd[i]
            elif flag % 2 == 0:
                if i in even:
                    return even[i]

            jump_pos = find_pos(i, flag)

            if jump_pos == n-1:
                return True
            elif 0 <= jump_pos < n-1:
                if (flag+1) % 2:
                    if jump_pos in even:
                        return even[jump_pos]
                elif (flag+1) % 2 == 0:
                    if jump_pos in odd:
                        return odd[jump_pos]

                check_res = check_pos(jump_pos, (flag+1) % 2)

                if (flag+1) % 2:
                    even[jump_pos] = check_res
                elif (flag+1) % 2 == 0:
                    odd[jump_pos] = check_res
                return check_res
            else:
                return False

        def find_pos(i, flag):
            minimal = float('inf')
            jump_pos = -1
            if flag == 1:
                for j in range(i+1, n):
                    if A[i] < A[j] and A[j]-A[i] < minimal:
                        minimal = A[j] - A[i]
                        jump_pos = j
            else:
                for j in range(i+1, n):
                    if A[j] < A[i] and A[i]-A[j] < minimal:
                        minimal = A[i] - A[j]
                        jump_pos = j
            return jump_pos

        for i in range(n-2, -1, -1):
            if check_pos(i, 1):
                res.append(i)

        return res


if __name__ == "__main__":
    print(Solution().solution([10, 13, 12, 14, 15]))
    print(Solution().solution([14, 13, 12, 14, 15]))
    print(Solution().solution([10, 11, 14, 11, 10]))
    print(Solution().solution([10, 12, 14, 13, 15]))
    print(Solution().solution([10, 11, 14, 11, 10]))