按要求生成表格，再用Kadane算法在各个方向上找出最大子列和并比较即可，结果是$52852124$。
注：以下为Python3代码，因用到Python3的函数缓存的特性（cache修饰词）。
from functools import *
def kadane(a):
m=c=0
for i in a:
c+=i
m=max(m,c)
c=max(0,c)
return m
@cache
def s(k):
return (100003-200003*k+300007*k*k*k)%1000000-500000 if k<=55 else (s(k-24)+s(k-55)+1000000)%1000000-500000
B=[[s(i*2000+j) for j in range(1,2001)] for i in range(2000)]
print("B done")
rowMax=max(kadane(B[i]) for i in range(2000))
print(rowMax)
colMax=max(kadane([B[i][j] for i in range(2000)]) for j in range(2000))
print(colMax)
diagSupMax=max(kadane([B[i][i+k] for i in range(2000-k)]) for k in range(2000))
print(diagSupMax)
diagSubMax=max(kadane([B[j+k][j] for j in range(2000-k)]) for k in range(1,2000))
print(diagSubMax)
antiDiagSupMax=max(kadane([B[i][k-i] for i in range(k)]) for k in range(2000))
print(antiDiagSupMax)
antiDiagSubMax=max(kadane([B[i][k-i-1] for i in range(k-2000,2000)]) for k in range(2001,4000))
print(antiDiagSubMax)
print(max(rowMax,colMax,diagSupMax,diagSubMax,antiDiagSupMax,antiDiagSubMax))
|
