Project Euler 149

http://projecteuler.net/index.php?section=problems&id=149

整数の列に対して部分列の和の最大を求める問題です。
列の長さをnとすると、部分列の決め方でO(n²)、和を取ってO(n³)の計算量になります。和は重複を避けるとO(n²)となります。しかし、これでもかなりの時間がかかってしまいます。
こういう列が与えられたとき、まず分割してなんとかならないか考えます。2つの分割した列に対してそれぞれ最大の和が求められたら、それを合成して全体の最大の和が求められる方法を考えればよいです。
単純に最大和を求めてもうまく合成できませんが、次のようにすればよいです。すなわち、全体の和、左端を含む（長さ0でもよい）最大の和、必ずしも端を含まない最大の和、右端を含む（長さ0でもよい）最大の和、が2つの隣接する部分列に対して得られれば、部分列を結合した列に対して同じ4つの和を得ることができます。
これで一つの列に対してO(n)、これがO(n)列あるので、計算量はO(n²)となりましたが、Pythonで計算させてみると4分ほどかかりました。恐らくPythonはこの手のリストの計算が非常に遅いです。C++で同じように組んだところ2秒弱でした。

from itertools import *

def gen_elements():
    a = [ int((100003 - 200003 * k + 300007 * k ** 3) % 1000000 - 500000)
                                            for k in range(1, 56) ]
    for k in xrange(55):
        yield a[k]
    
    while True:
        for k in xrange(55):
            l = k + 31 if k < 24 else k - 24
            a[k] = (a[l] + a[k] + 1000000) % 1000000 - 500000
            yield a[k]

def make_table():
    g = gen_elements()
    return [ list(islice(g, L)) for r in range(L) ]

def max_sum(a):
    def add(b, c):
        return (b[0] + c[0],
                max(b[1], b[0] + c[1]),
                max(max(b[2], c[2]), b[3] + c[1]),
                max(c[3], b[3] + c[0]))
    
    l = len(a)
    if l == 1:
        e = a[0]
        return (e,) * 4 if e > 0 else (e, 0, 0, 0)
    
    return add(max_sum(a[:l/2]), max_sum(a[l/2:]))

def gen_list(a):
    for e in a:
        yield e
    
    for i in xrange(L):
        yield [ e[i] for e in a ]
        yield [ a[i+j][j] for j in xrange(L - i) ]
        yield [ a[i][i+j] for j in xrange(L - i) ]
        yield [ a[j][i-j] for j in xrange(i + 1) ]
        yield [ a[L-j-1][i+j] for j in xrange(L - i) ]

L = 2000
a = make_table()
print max(max(max_sum(e)) for e in gen_list(a))