print(https://www.codechef.com/problems/PSPLIT)
A non-empty zero-indexed array A consisting of N integers is given. Any integer k, such that 0 <= K < N-1 , splits array A into two non-empty parts: A[0],A[1]...,A[K] and A[K+1],A[K+2],...,A[N-1]

The difference between the two parts is the value of abs(max{A[0],A[1],...A[K]} - max{A[K+1],A[K+2],...A[N-1]}), where abs is absolute difference function. For example in following Array A: {1,3,-3} Can be divided in two places:
For K=0, the first part contains just 1, and the second part contains numbers: 3 and -3. The difference is abs(1-3) = 2
For K=1, the first part contains numbers: 1 and 3 and the second part conatins just -3. The difference is abs (3-(-3)) = 6
Given a non empty zero indexed array A containing the N integers, find the maximum difference between the two parts into which it can be split. Lets call it a perfect split.

def solution2(A):
    max_right = max(A[1:])
    i_max_right = A.index(max_right)
    if i_max_right == len(A) - 1:
        return abs(max(A[:-1]) - A[i_max_right])

    max_left = A[0]
    max_diff = abs(max_left - max_right)

    for counter in range(1, len(A)):
        if counter > i_max_right:
            max_right = max(A[counter:])
            i_max_right = A.index(max_right)

        if abs(max_left - max_right) > max_diff:
            max_diff = max_left - max_right

        max_left = max(max_left, A[counter])

    return max_diff


def solution3(A):
    max_value = max(A)
    i_max_value = A.index(max_value)
    if i_max_value == len(A) - 1:
        return abs(max(A[:-1]) - A[i_max_value])

    last_value = A[-1]
    return abs(max_value - last_value)


if __name__ == "__main__":
    import time

    start = time.time()
    print(" --> quadratic")

    assert solution2([1, 3, -3]) == 6
    assert solution2([4, 3, 2, 5, 1, 1]) == 4
    assert solution2([4, 3, 2, 5, 1, 9]) == 4
    assert solution2([4, 3, 2, 5, 1, -4]) == 9
    assert solution2([0, 0]) == 0
    assert solution2([9, -4, -5]) == 14
    assert solution2([9, -4, 4]) == 5
    assert solution2([9, -4, 0]) == 9
    assert solution2([9, -4, 4]) == 5
    assert solution2([9, -4, 5]) == 4
    assert solution2(list(range(100))) == 1
    assert solution2(list(range(100000))) == 1
    assert solution2(list(range(100))[::-1]) == 99
    assert solution2(list(range(10000))[::-1]) == 9999
    assert solution3(list(range(100000, 0, -1))) == 99999

    assert solution2([-1000000000, -1000000000]) == 0
    assert solution2([1000000000, 1000000000]) == 0
    assert solution2([1000000000, -1000000000]) == 2000000000
    assert solution2([-1000000000, 1000000000]) == 2000000000

    end = time.time()
    print(end - start)
    start = time.time()
    print("----> Linear")
    assert solution3([1, 3, -3]) == 6
    assert solution3([4, 3, 2, 5, 1, 1]) == 4
    assert solution3([4, 3, 2, 5, 1, 9]) == 4
    assert solution3([4, 3, 2, 5, 1, -4]) == 9
    assert solution3([0, 0]) == 0
    assert solution3([9, -4, -5]) == 14
    assert solution3([9, -4, 4]) == 5
    assert solution3([9, -4, 0]) == 9
    assert solution3([9, -4, 4]) == 5
    assert solution3([9, -4, 5]) == 4
    assert solution3(list(range(100))) == 1
    assert solution3(list(range(100000))) == 1
    assert solution3(list(range(100))[::-1]) == 99
    assert solution3(list(range(10000))[::-1]) == 9999
    assert solution3(list(range(100000, 0, -1))) == 99999
    assert solution3([-1000000000, -1000000000]) == 0
    assert solution3([1000000000, 1000000000]) == 0
    assert solution3([1000000000, -1000000000]) == 2000000000
    assert solution3([-1000000000, 1000000000]) == 2000000000

    end = time.time()
    print(end - start)