Consider an array A
of length n
. The array contains only integers in the range 1
to s
. For example take s = 6
, n = 5
and A = (2, 5, 6, 3, 1)
. Let us define g(A)
as the collection of sums of all the non-empty contiguous subarrays of A. In this case g(A) = [2,5,6,3,1,7,11,9,4,13,14,10,16,15,17]
. The steps to produce g(A)
are as follows:
The subarrays of A are (2), (5), (6), (3), (1), (2,5), (5,6), (6,3), (3,1), (2,5,6), (5,6,3), (6,3,1),(2,5,6,3), (5,6,3,1), (2,5,6,3,1). Their respective sums are 2,5,6,3,1,7,11,9,4,13,14,10,16,15,17.
In this case all the sums are distinct.
However, if we looked at g((1,2,3,4))
then the value 3 occurs twice as a sum and so the sums are not all distinct.
Task
For each s
from 1 upwards, your code should output the largest n
so that there exists an array A of length n with distinct subarray sums.
Your code should iterate up from s = 1
giving the answer for each s
in turn. I will time the entire run, killing it after one minute.
Your score is the highest s
you get to in that time.
In the case of a tie, the first answer wins.
Examples
The answers for s = 1..12
are n=1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 9
.
Testing
I will need to run your code on my ubuntu machine so please include as detailed instructions as possible for how to compile and run your code.
Leaderboard
- s = 19 by Arnauld in C
9
and hard-coding an array of length 9? It's good practice to avoid unobservable requirements whenever possible, but it's rather difficult for some kinds of challenges (fastest-code, anything related to quines, etc.). \$\endgroup\$ – Dennis Nov 9 '18 at 15:48