Consider an array
A of length
n. The array contains only integers in the range
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.
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.
The answers for
s = 1..12 are
n=1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 9.
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.
- s = 19 by Arnauld in C