149. 最大和子序列(Maximum-sum Subsequence)
观察下面的表格，很容易验证在任何方向（水平、垂直、对角线或反对角线）上相邻数字的最大可能和为 \(16\)（\(= 8 + 7 + 1\)）。
\(-2\) \(5\) \(3\) \(2\) \(9\) \(-6\) \(5\) \(1\) \(3\) \(2\) \(7\) \(3\) \(-1\) \(8\) \(-4\) \(8\) 现在，让我们在更大的规模上重复这一搜索：
首先，使用一种称为"延迟斐波那契生成器"（Lagged Fibonacci Generator）的特定形式生成四百万个伪随机数：
对于 \(1 \le k \le 55\)，\(s\_k = [100003 - 200003 k + 300007 k^3] \pmod{1000000} - 500000\)。 对于 \(56 \le k \le 4000000\)，\(s\_k = [s\_{k-24} + s\_{k - 55} + 1000000] \pmod{1000000} - 500000\)。
因此，\(s\_{10} = -393027\) 且 \(s\_{100} = 86613\)。
然后将 \(s\) 的各项排列在一个 \(2000 \times 2000\) 的表格中，用前 \(2000\) 个数填充第一行（顺序），接下来的 \(2000\) 个数填充第二行，依此类推。
最后，找出在任何方向（水平、垂直、对角线或反对角线）上（任意数量）相邻项的（连续）最大和。
一、数学背景
本题的核心是经典的最大子数组和（Maximum Subarray Sum）问题，即给定一个一维数组，找出其连续子数组的最大和。
该问题的最优解法是 Kadane 算法，其核心思想是动态规划：设 \(dp[i]\) 表示以第 \(i\) 个元素结尾的最大子数组和，则：
即对于每个位置，要么从当前元素重新开始一个子数组，要么将当前元素接续到之前的子数组后面。空间上可以优化为只维护两个变量：max_ending_here 和 max_so_far，时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)（不含输入）。
本题将 Kadane 算法从一维扩展到二维网格的四个方向（水平、垂直、主对角线、反对角线），每个方向上的每条线独立求解，全局最大值为所有线上最大值的最大值。
二、算法设计
算法分为两个阶段：
阶段一：生成序列
延迟斐波那契生成器（LFG）生成 \(4{,}000{,}000\) 个整数：
- 前 \(55\) 项使用显式三次公式：\(s_k = (100003 - 200003k + 300007k^3) \bmod 10^6 - 500000\)
- 后续项使用递推：\(s_k = (s_{k-24} + s_{k-55} + 10^6) \bmod 10^6 - 500000\)
模 \(10^6\) 的结果在 \([0, 999999]\) 范围内，减去 \(500000\) 后得到 \([-500000, 499999]\) 范围内的值。
随后将一维序列重塑为 \(2000 \times 2000\) 的二维网格（按行填充）。
阶段二：扫描四个方向
对每个方向，用 Kadane 算法的迭代器版本扫描每条线：
- 水平方向：\(2000\) 行，每行 \(2000\) 个元素。
- 垂直方向：\(2000\) 列，每列 \(2000\) 个元素。
- 主对角线（左上到右下，\(r - c\) 为常数）：\(3999\) 条对角线，总元素数 \(4{,}000{,}000\)。
- 从顶行每个元素出发：\((0, c) \to (1, c+1) \to \cdots\)
- 从左列每个元素出发（跳过 \((0,0)\)）：\((r, 0) \to (r+1, 1) \to \cdots\)
- 反对角线（右上到左下，\(r + c\) 为常数）：\(3999\) 条反对角线，总元素数 \(4{,}000{,}000\)。
- 从顶行每个元素出发：\((0, c) \to (1, c-1) \to \cdots\)
- 从右列每个元素出发（跳过 \((0, N-1)\)）：\((r, N-1) \to (r+1, N-2) \to \cdots\)
使用生成器表达式按需生成每条线上的元素序列，避免创建临时列表，减少内存分配开销。
三、复杂度分析
| 阶段 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 生成序列 | \(O(N^2)\) | \(O(N^2)\) |
| 水平扫描 | \(O(N^2)\) | \(O(1)\)（迭代中） |
| 垂直扫描 | \(O(N^2)\) | \(O(1)\) |
| 对角线扫描 | \(O(N^2)\) | \(O(1)\) |
| 反对角线扫描 | \(O(N^2)\) | \(O(1)\) |
| 总计 | \(O(N^2)\) | \(O(N^2)\) |
其中 \(N = 2000\)，\(N^2 = 4{,}000{,}000\)。总操作量约 \(4 \times 4{,}000{,}000 = 1.6 \times 10^7\) 次比较，在现代硬件上完成仅需数秒。
四、代码实现与说明
"""
Project Euler Problem 149: Maximum-sum Subsequence
For a 2000x2000 grid generated by a Lagged Fibonacci Generator,
find the maximum contiguous subarray sum in any of the four directions
(horizontal, vertical, main diagonal, anti-diagonal).
"""
def generate_sequence(size: int = 4_000_000) -> list[int]:
"""
Generate the Lagged Fibonacci sequence s_k for k = 1 to size.
For 1 <= k <= 55:
s_k = (100003 - 200003*k + 300007*k^3) mod 1000000 - 500000
For 56 <= k <= size:
s_k = (s_{k-24} + s_{k-55} + 1000000) mod 1000000 - 500000
"""
MOD = 1_000_000
HALF = 500_000
s = [0] * size
for k in range(1, 56):
val = (100003 - 200003 * k + 300007 * k * k * k) % MOD - HALF
s[k - 1] = val
for k in range(56, size + 1):
val = (s[k - 24 - 1] + s[k - 55 - 1] + MOD) % MOD - HALF
s[k - 1] = val
return s
def kadane(arr):
"""
Return the maximum subarray sum of an iterable using Kadane's algorithm.
For an empty sequence, returns negative infinity.
For a single-element sequence, returns that element.
"""
it = iter(arr)
try:
max_ending_here = max_so_far = next(it)
except StopIteration:
return float('-inf')
for x in it:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
def solve() -> int:
"""Return the maximum subarray sum in any direction in the 2000x2000 grid."""
N = 2000
total = N * N
seq = generate_sequence(total)
grid = [seq[i * N:(i + 1) * N] for i in range(N)]
del seq
best = float('-inf')
# 1. Horizontal
for r in range(N):
best = max(best, kadane(grid[r]))
# 2. Vertical
for c in range(N):
best = max(best, kadane(grid[r][c] for r in range(N)))
# 3. Main diagonals (top-left to bottom-right)
for c in range(N):
best = max(best, kadane(grid[r][c + r] for r in range(N - c)))
for r in range(1, N):
best = max(best, kadane(grid[r + d][d] for d in range(N - r)))
# 4. Anti-diagonals (top-right to bottom-left)
for c in range(N):
best = max(best, kadane(grid[r][c - r] for r in range(c + 1)))
for r in range(1, N):
best = max(best, kadane(grid[r + d][N - 1 - d] for d in range(N - r)))
return best
if __name__ == "__main__":
# Verify with the 4x4 sample grid
sample = [
[-2, 5, 3, 2],
[9, -6, 5, 1],
[3, 2, 7, 3],
[-1, 8, -4, 8],
]
n = 4
best = float('-inf')
for r in range(n):
best = max(best, kadane(sample[r]))
for c in range(n):
best = max(best, kadane(sample[r][c] for r in range(n)))
for c in range(n):
best = max(best, kadane(sample[r][c + r] for r in range(n - c)))
for r in range(1, n):
best = max(best, kadane(sample[r + d][d] for d in range(n - r)))
for c in range(n):
best = max(best, kadane(sample[r][c - r] for r in range(c + 1)))
for r in range(1, n):
best = max(best, kadane(sample[r + d][n - 1 - d] for d in range(n - r)))
assert best == 16, f"Sample verification failed: got {best}, expected 16"
print("Sample test passed:", best)
# Verify known sequence values
seq = generate_sequence(100)
assert seq[9] == -393027, f"s_10 failed: got {seq[9]}"
assert seq[99] == 86613, f"s_100 failed: got {seq[99]}"
print("Sequence verification passed.")
result = solve()
print("Answer:", result)
代码说明：
generate_sequence
- 生成长度为 \(4{,}000{,}000\) 的 LFG 序列。
- 前 \(55\) 项使用显式公式，注意 Python 中
%对负数返回非负余数，减去500000得到目标范围。 - 后续项使用滑动窗口递推：\(s_k\) 依赖于 \(s_{k-24}\) 和 \(s_{k-55}\)（都是已经计算好的前驱值）。
kadane
- 接受任意可迭代对象，返回其最大子数组和。
- 处理空序列的边界情况（返回负无穷）。
- 单次扫描，每步做两次比较：
max(x, max_ending_here + x)和max(max_so_far, max_ending_here)。
主对角线迭代
- 从顶行 \((0, c)\) 出发：沿
grid[r][c + r]向下移动，直到 \(r\) 达到边界。 - 从左列 \((r, 0)\) 出发（跳过已覆盖的 \((0, 0)\)）：沿
grid[r + d][d]移动。
反对角线迭代
- 从顶行 \((0, c)\) 出发：沿
grid[r][c - r]向下移动，直到 \(r\) 超过 \(c\)。 - 从右列 \((r, N-1)\) 出发（跳过已覆盖的 \((0, N-1)\)）：沿
grid[r + d][N-1-d]移动。
验证部分
- 用问题中给出的 \(4 \times 4\) 样本网格验证算法正确性，期望结果为 \(16\)。
- 验证序列生成器：\(s_{10} = -393027\)，\(s_{100} = 86613\)。