p149

p149.py

def MaxContiguousSubarray(A):
    currMax = 0 
    currSum = 0
    for i in range(len(A)):
        currSum = max(currSum + A[i], A[i])
        currMax = max(currMax, currSum)
    return currMax

def MaxsumSubseq(M):
    currMax = 0
    l = len(M[0])
    for i in range(l):
        currMax = max(currMax,
                      MaxContiguousSubarray(M[i]), #Horizontal
                      MaxContiguousSubarray([M[j][i] for j in range(l)]), #Vertical
                      MaxContiguousSubarray([M[l - j - 1][i - j - 1] for j in range(i + 1)]), #Diagonal
                      MaxContiguousSubarray([M[i + j][i + j] for j in range(l - i)]), #Diagonal
                      MaxContiguousSubarray([M[l - j - 1][l - i + j - 1] for j in range(i + 1)]), #Anti-Diagonal
                      MaxContiguousSubarray([M[j][i - j] for j in range(i + 1)]) #Anti-Diagonal
                                            )
    return currMax
  
def genM():
    M = [[0 for _ in range(2000)] for _ in range(2000)]
    S = [0] + [0]*(4*10**6)

    for k in range(1, 56):
        S[k] = (100003 - 200003*k + 300007*pow(k, 3, 10**6)) % 10**6 - 500000
    
    for k in range(56, 4*10**6 + 1):
        S[k] = (S[k - 24] + S[k - 55]) % 10**6 - 500000
    
    S.pop(0)
    for i, s in enumerate(S):
        M[i//2000][i % 2000] = s
        
print(MaxsumSubseq(genM())