Given an array of positive integers you are allowed to increase any element by one for once, your goal is to maximize the multiplication of all the elements For example:
Input:
$5$
$1$ $6$ $5$ $8$ $1$
Output:
$2$ $6$ $5$ $8$ $1$
Greedy solution:
increase the minimum element of the array
Can anyone proof this solution?
If the elements of the array are $x_1,x_2,\cdots,x_n$, we want to maximize $$x_1x_2\cdots x_{r-1}(1+x_r)x_{r+1}\cdots x_n$$
$$=x_1x_2x_3\cdots x_n(1+\frac{1}{x_r})$$
Since the first part is constant, we want to maximize $1+\frac{1}{x_r}$, that is, we want to minimize $x_r$.