How can I maximize this expression? 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)$?
 A: 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.
A: 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)$$
