A question about cardinality of differences of subsets of $\{1,\cdots, n\}$ Let $n\in\mathbb{N}$ and for every $1\leq i\leq n$, let $A_i=\{1,\cdots, i\}$.
For every sequence of distinct numbers $i_1,\cdots,i_k\in\mathbb{N}$, let
 $$M(i_1,\cdots,i_k)=(A_{i_1}\setminus A_{i_2})\cup (A_{i_2}\setminus A_{i_3})\cup\cdots\cup (A_{i_{k-1}}\setminus A_{i_k})\cup(A_{i_k}\setminus A_{i_1}). $$ 
What is the maximum value of 
$$ |M(i_1,\cdots,i_{k_1})|+|M(i_{k_1+1},\cdots,i_{k_1+k_2})|+\cdots
+|M(i_{k_1+\cdots+k_s+1},\cdots,i_{k_1+\cdots+k_{s+1}})|,$$
where $k_1+\cdots+k_{s+1}=n$ and 
$$ \{i_1,\cdots,i_{k_1},\cdots,i_{k_1+k_2},\cdots,i_{k_1+k_2+\cdots
k_{s+1}}\}=\{1,\cdots n\}?$$
 A: The maximum value which we are looking for is $\left\lfloor\tfrac {n^2}4\right\rfloor$.
The question is easy to answer provided we choose a right way to deal with it. It is based on a few insights. It is easy to see that each partial instance of the sum of absolute values 
$$|M(i_1,\cdots,i_{k_1})|+|M(i_{k_1+1},\cdots,i_{k_1+k_2})|+\cdots
+|M(i_{k_1+\cdots+k_s+1},\cdots,i_{k_1+\cdots+k_{s+1}})|$$
equals to $M(\sigma)=\sum_{i=1}^n \max\{i-\sigma(i),0\}$, where $\sigma $ is a permutation of the set $[n]=\{1,\dots,n\}$ whose (unique) decomposition of a product of mutually disjoint cycles is 
$$(i_1,\cdots,i_{k_1}) (i_{k_1+1},\cdots,i_{k_1+k_2})\cdots  (i_{k_1+\cdots+k_s+1},\cdots,i_{k_1+\cdots+k_{s+1}}).$$
Let $A=\{i\in [n]:\sigma(i)\ge i\}$. Then $M(\sigma)=\sum_{i\in A} i-\sigma(i)=\sum_{i\in A} i-\sum_{i\in \sigma(A)} i$. Let $s=|A|$. Then 
$$\sum_{i\in A} i\le \sum_{i=n-s+1}^n i\mbox{ and }\sum_{i\in \sigma(A)} i\ge \sum_{i=1}^s i \tag{*}\label{*},$$
so $$M(\sigma)=\sum_{i\in A} i- \sum_{i\in \sigma(A)} i\le \sum_{i=1}^s n+1-i-\sum_{i=1}^s i=$$ $$
\sum_{i=1}^s n+1-2i=s(n+1)-s(s+1)=s(n-s).$$
The function $f(s)=s(n-s)$ has a parabolic graph and a maximum at $s=n/2$. This implies that $ M(\sigma)\le M=\max\{f(s):s\in [n]\}$, which is attained  when $n=2s$ if $n$ is even or $n=2s\pm 1$, if $n$ is odd. Anyway, $M=\left\lfloor\tfrac {n^2}4\right\rfloor$. On the other hand, it is easy to see that when $\sigma(i)=n+1-i$ for each $i\in [n]$ then $A=\left\{\left\lfloor\tfrac n2\right\rfloor, \left\lfloor\tfrac n2\right\rfloor+1,\dots, n\right\}$, $s=\left\lfloor\tfrac {n+1}2\right\rfloor$, so the inequalities (\ref{*}) and $f(s)\le M$  became equalities.
