def gen_numbers():
    numbers = []
    for k in range(1, 56):
        n = (100_003 - 200_003*k + 300_007*k**3) % 1_000_000 - 500_000
        numbers.append(n)
    for k in range(56, 2000 * 2000 + 1):
        n = (numbers[k-24-1] + numbers[k-55-1] + 1_000_000) % 1_000_000 - 500_000
        numbers.append(n)
    return numbers


def split(xs, n):
    return [xs[i:i + n] for i in range(0, len(xs), n)]


def diags(rows):
    n = len(rows)
    diags = []
    for col_i in range(-n + 1, n):
        d = []
        for row_i in range(n):
            if col_i >= 0 and col_i < n:
                d.append(rows[row_i][col_i])
            col_i += 1
        diags.append(d)
    return diags


def anti_diags(rows):
    n = len(rows)
    diags = []
    for col_i in range(-n + 1, n):
        d = []
        for row_i in range(n - 1, -1, -1):
            if col_i >= 0 and col_i < n:
                d.append(rows[row_i][col_i])
            col_i += 1
        diags.append(d)
    return diags


def shorten(xs):
    r = []
    i = 0
    while i < len(xs):
        r.append(0)
        if xs[i] < 0:
            while i < len(xs) and xs[i] < 0:
                r[-1] += xs[i]
                i += 1
        else:
            while i < len(xs) and xs[i] >= 0:
                r[-1] += xs[i]
                i += 1
    if r[0] <= 0:
        r = r[1:]
    if r and r[-1] <= 0:
        r = r[:-1]
    return r


def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray.

    https://en.wikipedia.org/wiki/Maximum_subarray_problem

    Emberassing that I didn't come up with that myself...
    """
    best_sum = -10**12
    current_sum = 0
    for x in numbers:
        current_sum = max(x, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum


def max_subarray_naiv(xs):
    """ Naiv implementation in O(n^3) or something. """
    r = 0
    xs = shorten(xs)
    for width in range(1, len(xs) + 1, 2):
        for i in range(len(xs)):
            r = max(r, sum(xs[i:i+width]))
    return r


def euler_149():
    ns = gen_numbers()
    assert ns[10-1] == -393027
    assert ns[100-1] == 86613

    rows = split(ns, 2000)
    cols = list(map(list, zip(*rows)))

    r = 0
    for elems in [rows, cols, diags(rows), anti_diags(rows)]:
        for xs in elems:
            r = max(max_subarray(xs), r)
    return r


if __name__ == "__main__":
    solution = euler_149()
    print("e149.py: " + str(solution))
    assert solution == 52852124