Find arrays with distinct subarray sums

Question

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

Answer 1

C (gcc), s = 19

This is basically a port of my Node.js answer. It goes one step further with the default compiler options and two steps further with -O2 or -O3.

#include <stdio.h>
#include <string.h>
#include <stdint.h>

void search(uint8_t * arr, int n, uint8_t * sum, int * max, char * str, int depth) {
  int i, j, k, s;
  char tmp[16];

  // do we have a better array?
  if(depth > *max) {
    for(str[0] = '\0', i = 0; i < depth; i++) {
      sprintf(tmp, "%d ", arr[i]);
      strcat(str, tmp);
    }
    *max = depth;
  }

  // try to append i = 1 to n to the current array
  for(i = 1; i <= n; i++) {
    // provided that doing so does not produce a sum that was already encountered
    if(!sum[i]) {
      for(sum[s = i] = 1, j = depth; j && !sum[s += arr[j - 1]]; j--) {
        sum[s] = 1;
      }
      if(!j) {
        // this is valid: set the value in arr[] and do a recursive call
        arr[depth] = i;
        search(arr, n, sum, max, str, depth + 1);
      }
      // whether the recursive call was processed or not, we have to clear the flags
      // that have been set above
      for(sum[s = i] = 0, k = depth - 1; k >= j; k--) {
        sum[s += arr[k]] = 0;
      }
    }
  }
}

int solve(int n, char * str) {
  int     max = 0;              // best length so far
  int     hi = n * (n + 1) / 2; // highest possible sum for n
  uint8_t sum[hi + 1];          // encountered sums
  uint8_t arr[n];               // array

  memset(sum, 0, (hi + 1) * sizeof(uint8_t));
  search(arr, n, sum, &max, str, 0);

  return max;
}

/////////////////////////////////////////////////////////////////////////////////////

void main() {
  char str[128];
  int  n, res;

  for(n = 1; n <= 19; n++) {
    res = solve(n, str);
    printf("N = %d --> %d with [ %s]\n", n, res, str);
  }
}

Try it online!

Answer 2

Node.js, s = 17

Just a simple recursive search to get the ball rolling. Returns both the length and a valid array.

solve = n => {
  var max = 0,  // best length so far
      best,     // best array so far
      sum = {}; // encountered sums

  (search = a => {
    var i, j, k, s;

    // do we have a better array?
    if(a.length > max) {
      max = a.length;
      best = [...a];
    }

    // try to prepend i = 1 to n to the current array
    for(i = 1; i <= n; i++) {
      // provided that doing so does not produce a sum that was already encountered
      if((sum[j = 0, s = i] ^= 1) && a.every(n => sum[j++, s += n] ^= 1)) {
        search([i, ...a]);
      }
      // reset the flags that have been toggled above
      for(sum[s = i] ^= 1, k = 0; k < j; k++) {
        sum[s += a[k]] ^= 1;
      }
    }
  })([]);

  return [ max, best ];
}

Try it online!