关注公众号【算法码上来】，每日算法干货马上就来！
今天讲了多重求和，也就是一个和式由多个下标来指定。
首先是最简单的形式：
<!–swig0–>
例题1
下面给出一个对称矩阵：
<!–swig1–>
求：
<!–swig2–>
这是这个矩阵的上三角加对角线求和，因为是对称的嘛，可以补全下三角，加上对角线就行了。
<!–swig3–>
所以
<!–swig4–>
例题2
下面再看一个例子：
<!–swig5–>
同样模仿上例调换$j,k$位置，得到：
<!–swig7–>
所以
<!–swig8–>
至此解完，然后可以推出一个著名的不等式————切比雪夫不等式：
<!–swig9–>
如果
<!–swig10–>
那么
<!–swig11–>
反之如果
<!–swig12–>
那么
<!–swig13–>
更一般的结论，给定两个序列$a$和$b$，求下面式子最大值与最小值：
<!–swig16–>
其中$p(k)$是$\{ 1,2, \cdots ,n\} $的一个排列。
答案是$b$增序最大，降序最小，至于为什么，下面给出两种证明方法。
方法1
如上图所示，$a$和$b$按照递增顺序排列，每个方格的面积代表$a_i$与$b_j$的乘积，记为$s_{ij}$。
那么上面的求和式其实就是每一行每一列都必须有且只有一块被取。
考虑第一行，如果不取$s_{11}$，取其他的$s_{1j}$，那么第一列也只能取其他的$s_{i1}$，这样的话$s_{ij}$也就取不了了。但是发现
<!–swig29–>
并且两种取法影响的行和列都是相同的，这说明了，取$s_{i1}$和$s_{1j}$不如取$s_{11}$和$s_{ij}$。所以$s_{11}$必取，然后第一行第一列就不能取了。剩下的方阵用相同的方法可以得出必取$s_{22}, \cdots ,s_{nn}$，也就是主对角线。
同理最小取法用副对角线可以推出。
方法2
设数列$a$和$b$非单调递减，那么有如下证明：
<!–swig38–>
反之亦证。
题外话，其实切比雪夫不等式原来是以微积分形式给出的：
如果函数$f(x)$和$g(x)$非单调递减，那么有：
<!–swig41–>
例题3
求
<!–swig42–>
我将用三种方法来求解这个式子。
方法1
首先将$j$和$k$分开，首先计算对$j$求和：
<!–swig46–>
方法2
先计算对$k$求和：
<!–swig48–>
方法3
按对角线求和：
<!–swig49–>
由此得到了一个完全不同的表示形式！
所以我们得到了：
<!–swig50–>
