设集合\(A\)中有\(n\)个元素，将其中每个元素进行编号为\(a_x\) \(\left ( x\in \left [ 1,n \right ] \right )\) :
\[\begin{aligned}
A=\begin{Bmatrix}
a_1,&a_2, &a_3, &\cdot &\cdot &\cdot &a_{n-1}, &a_n
\end{Bmatrix}
\end{aligned}
\]
1.若\(A\)是一条递增序列，则删除最后一个数，其代表的数值\(S_A\)最小。
首先，将\(S_A\)通过\(A\)表示：
\[\begin{aligned}
S_A=a_1\times 10^{n-1}+a_2\times 10^{n-2}+\cdot \cdot \cdot +a_{n-1}\times10+a_n
\end{aligned}
\]
若删去最后一个数，序列\(A\)变为\(A‘\)，记新表示的数为\(S_{A‘}\)，则：
\[\begin{aligned}
S_{A‘}=a_1\times 10^{n-2}+a_2\times 10^{n-3}+\cdot \cdot \cdot +a_{n-2}\times10+a_{n-1}
\end{aligned}
\]
若所删除的数，不是最后一个数\(a_n\)，而是任意一个数\(a_q\)，序列\(A\)变为\(A‘‘\)，记新表示的数为\(S_{A‘‘}\)，则：
\[\begin{aligned}
S_{A‘‘}=a_1\times 10^{n-2}+a_2\times 10^{n-3}+\cdot \cdot \cdot +a_{q-1}\times10^{n-q}+a_{q+1}\times10^{n-q-1} \cdot\cdot \cdot +a_{n-2}\times10+a_{n-1}
\end{aligned}
\]
然后观察两式，可以看出来：\(S_{A‘}\) 与\(S_{A‘‘}\)前\(q\)项是相同的，故作差：
\[\begin{aligned}
S_{A‘}-S_{A‘‘}=\left ( a_q-a_{q+1} \right )\times10^{n-q-1}+\left ( a_{q+1}-a_{q+2} \right )\times10^{n-q-2} \cdot\cdot \cdot +\left ( a_{n-2}-a_{n-1} \right )\times10+\left ( a_{n-1}-a_n \right )
\end{aligned}
\]
因为，序列\(A\)是递增的，所以：
\[\begin{aligned}
a_q\leq a_{q+1}\leq a_{q+2}\cdot \cdot \cdot a_{n+1}\leq a_n
\end{aligned}
\]
即：
\[\begin{aligned}
a_q-a_{q+1}\leq0, a_{q+1}-a_{q+2}\leq0, \cdot \cdot \cdot a_{n+1}-a_n\leq 0
\end{aligned}
\]
所以：\(S_{A‘}-S_{A‘‘}\leq0\)，所以\(S_{A‘} \leq S_{A‘‘}\)
所以，若\(A\)是一条递增序列，则删除最后一个数，其代表的数值\(S_A\)最小。
2.若\(A\)是一条递减序列，则删除第一个数，其代表的数值\(S_A\)最小。
证明方法与 1 同理。
3.由1,2可以猜想：如果\(A\)中存在\(a_1-a_i\)为单调增，\(a_{i+1}-a_n\)为单调减。
单调增的部分，应该删去最后一个数。单调减的部分，应该删去最初一个数。
我们会发现，这两个结论其实是统一的：如下图，应该删去折点所表示的数，也就是“山峰”。
如果我们删除一个数\(a_q\)，位于\(a_q\)之前的数就会往后一位，得到\(S_{A‘}\)
如果我们删除“山峰”\(a_i\)，位于\(a_i\)之前的数就会往后一位，得到\(S_{A‘‘}\)
对比两图可以发现：\(S_{A‘‘}-S_{A‘}\)后，黄颜色框中的部分便消去了。即得到与 1证明 中类似的差值。
即\(S_{A‘‘}\leq S_{A‘}\)。
所以，若\(A\)不存在单调性，则删除“山峰”，其代表的数值\(S_A\)最小。
删数问题的贪心策略正确性证明
原文：https://www.cnblogs.com/cyl-oi-miracle/p/13522630.html
