The answer is $M = n + 1$.

$|S| \ge n + 1$, since if Alice selects
$$(y_1, y_2, \dots, y_n) = \underbrace{(0, 0, \dots, 0)}_{k\ 0's}, 1, 1, \dots, 1)$$
$$(x_1, x_2, \dots, x_n) = \underbrace{(-1, -1, \dots, -1)}_{k\ (-1)'s}, 1, 1, \dots, 1),$$
where $0 \le k \le n$, then Bob can only win if $(z_1, z_2, \dots, z_n) = (y_1, y_2, \dots, y_n)$, so $S$ contains $(0, 0, \dots, 0, 1, 1, \dots, 1)$. Now, suppose $S$ only contains elements of that form. It remains to show that Bob can win. Rewrite the inequality as:
$$\sum_{i=1}^{n} (y_i - y_{i-1})(x_i + \dots + x_n) \le \sum_{i=1}^{n} (z_i - z_{i-1})(x_i + \dots + x_n),$$
where $y_0 = z_0 = 0$ for convenience. Note that from the choice of $S$, $z_i - z_{i-1} = 1$ for exactly one index $i$, and $0$ for the others. However,
$$\sum_{i=1}^{n} (y_i - y_{i-1})(x_i + \dots + x_n) \le \left( \sum_{i=1}^{n} (y_i - y_{i-1}) \right) \max_{1 \le i \le n} (x_i + \dots + x_n) \le \max_{1 \le i \le n} (x_i + \dots + x_n).$$
Whatever Alice's choices are, Bob can always pick precisely the $i$ that attains that maximum and wins.