---

Problem 150

---

Searching a triangular array for a sub-triangle having minimum-sum

In a triangular array of positive and negative integers, we wish to find a sub-triangle such that the sum of the numbers it contains is the smallest possible.

In the example below, it can be easily verified that the marked triangle satisfies this condition having a sum of -42.

We wish to make such a triangular array with one thousand rows, so we generate 500500 pseudo-random numbers s_k in the range ±2¹⁹, using a type of random number generator (known as a Linear Congruential Generator) as follows:

t := 0
for k = 1 up to k = 500500:
  t := (615949*t + 797807) modulo 2²⁰
  s_k := t-2¹⁹

Thus: s₁ = 273519, s₂ = -153582, s₃ = 450905 etc

Our triangular array is then formed using the pseudo-random numbers thus:

s₁ s₂  s₃ s₄  s₅  s₆  s₇  s₈  s₉  s₁₀ ...

Sub-triangles can start at any element of the array and extend down as far as we like (taking-in the two elements directly below it from the next row, the three elements directly below from the row after that, and so on).
The “sum of a sub-triangle” is defined as the sum of all the elements it contains.
Find the smallest possible sub-triangle sum.

---

寻找三角形数组的最小和子三角形

我们希望在一个包含正数和负数的三角形数组中找到一个子三角形，其中元素的和尽可能小。

在下面这个例子中，可以验证带标记的三角形满足题述，它的元素和是-42。

我们希望搭建起一个有一千行的三角形数组，因此我们使用一种随机数生成算法（称为线性同余生成器），生成了500500个在范围±2¹⁹之间的伪随机数s_k，如下所示：

t := 0
for k = 1 up to k = 500500:
  t := (615949*t + 797807) modulo 2²⁰
  s_k := t-2¹⁹

因此，s₁ = 273519，s₂ = −153582，s₃ = 450905，依此类推。

接下来就将这些伪随机数填入三角形数组：

s₁ s₂  s₃ s₄  s₅  s₆  s₇  s₈  s₉  s₁₀ ...

子三角形可以从数组中的任意元素开始，向下可以延伸至无限长（先取下一行的两个元素，再取接下来一行的三个元素，依此类推）。
“子三角形的和”被定义为其中所有元素的和。
求最小的子三角形的和。

---