How can I maximize this expression?

Question

Let $d_1,...,d_n$ be non-negative integers such that $d_1 + ... + d_n = n -1$ and $d_{i} \leq i$. What is the value of the following expression: $\sum_{i=1}^n d_i (n - i)$ when maximized (a good asymptotic approximation is fine)? Is it $O(n^2)$?

Answer 1

Denote $S_k=\displaystyle\sum_{i=1}^{k}d_i, k=1,2,...,n$, then we have $\displaystyle\sum_{i=1}^{n}d_i(n-i)=\displaystyle\sum_{k=1}^{n-1}S_k$.

Since $0\leq d_i\leq i\Rightarrow S_k\leq\displaystyle\sum_{i=1}^{k}i=\frac{k(k+1)}2$, also we have $S_k\leq S_n=n-1$.

So, $S_k\leq\min\left(\frac{k(k+1)}2,n-1\right)$. And there must be a integer $m$ such that $$m(m+1)\leq2(n-1)<(m+1)(m+2)$$ then $\displaystyle\sum_{k=1}^{n-1}S_k=\displaystyle\sum_{k=1}^{m}S_k+\displaystyle\sum_{k=m+1}^{n-1}S_k\leq\displaystyle\sum_{k=1}^{m}\frac{k(k+1)}2+(n-1)(n-1-m)$ $$=\frac1{2}\sum_{k=1}^{m}(k^2+k)+(n-1)(n-1-m)$$ $$=\frac1{2}\left(\frac{m(m+1)(2m+1)}6+\frac{m(m+1)}2\right)+(n-1)(n-1-m)$$ $$=\frac{m(m+1)(m+2)}6+(n-1)(n-1-m)$$ The equality holds while $d_i=i, (i<m+1), d_{m+1}=n-1-\frac{m(m+1)}2$ and $d_i=0, (i>m+1)$

To get a good approximation, use $m^2<2(n-1)<(m+2)^2$, we can obtain $$\sqrt{2(n-1)}-2<m<\sqrt{2(n-1)}\Longrightarrow\left[\sqrt{2(n-1)}\right]-1\leq m+1\leq\left[\sqrt{2(n-1)}\right]+1$$ Thus, it is reasonable to use $m+1=\left[\sqrt{2(n-1)}\right]$ to estimate the maximum vaule, which is $$\frac{m(m+1)(m+2)}6+(n-1)(n-1-m)$$ $$\approx\frac{\left[\sqrt{2(n-1)}\right](2n-3)}6+(n-1)(n-\left[\sqrt{2(n-1)}\right])$$ $$=n^2-n-\frac{4n-3}6\left[\sqrt{2(n-1)}\right]=O(n^2)$$

Answer 2

To maximize the objective $\sum_{i=1}^{n}d_{i}(n-i)$, we want to put as much weight as possible in the first $d_{i}$s. But there is a constraint that $d_{i} \le i$; otherwise we would set $d_{1}= n-1$, i.e., use the entire budget on $d_{1}$.

Under the constraint, the best policy is to set $d_{1}=1$, $d_{2}=2,\dots$. But we have a specific budget, so we cannot do that for all $d_{i}$s. Instead we can do it for the first $m$ $d_{i}$s and then set $d_{i}=0$ for all $i>m$. How do we know $m$?

Since we assign $d_{i}=i$ for all $i\le m$, then $m$ must be such that $$ \sum_{i=1}^{m}i \le n-1. $$ But, $$ \sum_{i=1}^{m}i = m(m+1)/2. $$ Can you get an upper bound on $m$? (Note that if you will have some left-over budget to use on $d_{m+1}$, but you can factor that in and it will not change your asymptotic result).

In any case, you should be able to show that $m=\Theta(\sqrt{n})$. Then, $$ \sum_{i=1}^{m}i(n-i) \le \sum_{i=1}^{n}d_{i}(n-i) \le \sum_{i=1}^{m+1}i(n-i). $$ Also, for the lower bound (and similarly for the upper bound) $$ \sum_{i=1}^{m}i(n-i) = n\sum_{i=1}^{m}i - \sum_{i=1}^{m}i^{2}. $$ The sums in the right hand side have a closed form solution. You should be able to take it from here.