← 完整题目索引

PROJECT EULER · #0149

最大和子序列

Maximum-sum Subsequence

仅题目 · 已解决原题 ↗

查看下表,很容易验证任何方向(水平、垂直、对角线或反对角线)相邻数字的最大可能总和16 (=8+7+1)。

2532
9651
32 73
1848

现在,让我们重复搜索,但规模要大得多:

首先,使用所谓的"滞后斐波那契生成器"的特定形式生成四百万个伪随机数:

对于 1k55sk=[100003200003k+300007k3](mod1000000)500000
对于 56k4000000sk=[sk24+sk55+1000000](mod1000000)500000

因此,s10=393027s100=86613

然后将 s 的项排列在 2000×2000 表中,使用前 2000 数字填充第一行(按顺序),接下来的 2000 数字填充第二行,依此类推。

最后,找到任意方向(水平、垂直、对角线或反对角线)上(任意数量)相邻条目的最大总和。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。