106 lines
2.4 KiB
Python
106 lines
2.4 KiB
Python
def gen_numbers():
|
|
numbers = []
|
|
for k in range(1, 56):
|
|
n = (100_003 - 200_003*k + 300_007*k**3) % 1_000_000 - 500_000
|
|
numbers.append(n)
|
|
for k in range(56, 2000 * 2000 + 1):
|
|
n = (numbers[k-24-1] + numbers[k-55-1] + 1_000_000) % 1_000_000 - 500_000
|
|
numbers.append(n)
|
|
return numbers
|
|
|
|
|
|
def split(xs, n):
|
|
return [xs[i:i + n] for i in range(0, len(xs), n)]
|
|
|
|
|
|
def diags(rows):
|
|
n = len(rows)
|
|
diags = []
|
|
for col_i in range(-n + 1, n):
|
|
d = []
|
|
for row_i in range(n):
|
|
if col_i >= 0 and col_i < n:
|
|
d.append(rows[row_i][col_i])
|
|
col_i += 1
|
|
diags.append(d)
|
|
return diags
|
|
|
|
|
|
def anti_diags(rows):
|
|
n = len(rows)
|
|
diags = []
|
|
for col_i in range(-n + 1, n):
|
|
d = []
|
|
for row_i in range(n - 1, -1, -1):
|
|
if col_i >= 0 and col_i < n:
|
|
d.append(rows[row_i][col_i])
|
|
col_i += 1
|
|
diags.append(d)
|
|
return diags
|
|
|
|
|
|
def shorten(xs):
|
|
r = []
|
|
i = 0
|
|
while i < len(xs):
|
|
r.append(0)
|
|
if xs[i] < 0:
|
|
while i < len(xs) and xs[i] < 0:
|
|
r[-1] += xs[i]
|
|
i += 1
|
|
else:
|
|
while i < len(xs) and xs[i] >= 0:
|
|
r[-1] += xs[i]
|
|
i += 1
|
|
if r[0] <= 0:
|
|
r = r[1:]
|
|
if r and r[-1] <= 0:
|
|
r = r[:-1]
|
|
return r
|
|
|
|
|
|
def max_subarray(numbers):
|
|
"""Find the largest sum of any contiguous subarray.
|
|
|
|
https://en.wikipedia.org/wiki/Maximum_subarray_problem
|
|
|
|
Emberassing that I didn't come up with that myself...
|
|
"""
|
|
best_sum = -10**12
|
|
current_sum = 0
|
|
for x in numbers:
|
|
current_sum = max(x, current_sum + x)
|
|
best_sum = max(best_sum, current_sum)
|
|
return best_sum
|
|
|
|
|
|
def max_subarray_naiv(xs):
|
|
""" Naiv implementation in O(n^3) or something. """
|
|
r = 0
|
|
xs = shorten(xs)
|
|
for width in range(1, len(xs) + 1, 2):
|
|
for i in range(len(xs)):
|
|
r = max(r, sum(xs[i:i+width]))
|
|
return r
|
|
|
|
|
|
def euler_149():
|
|
ns = gen_numbers()
|
|
assert ns[10-1] == -393027
|
|
assert ns[100-1] == 86613
|
|
|
|
rows = split(ns, 2000)
|
|
cols = list(map(list, zip(*rows)))
|
|
|
|
r = 0
|
|
for elems in [rows, cols, diags(rows), anti_diags(rows)]:
|
|
for xs in elems:
|
|
r = max(max_subarray(xs), r)
|
|
return r
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_149()
|
|
print("e149.py: " + str(solution))
|
|
assert solution == 52852124
|