思路

题目要求枚举左右端点，求解出所有的区间和，这使得每个位置在区间中的贡献不同。例如，当 $n=3$ 时，所有的子区间为 $[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]$。其中，位置$1$贡献$2$次，位置$2$贡献$4$次，位置$3$贡献$2$次。题目要求最小化总代价，因此需要让较大的数贡献较少的次数。将较大的数放在贡献次数少的位置，比如将较大的数放在位置$1$和$3$，较小的数放在贡献次数较多的位置$2$。

对于每个位置，统计其贡献次数，然后通过排序将数值大的数放置在贡献次数少的位置。对于位置$i$，包含$i$的区间$[l, r]$满足$l \leq i \leq r$，因此有$0 \leq l \leq i, i \leq r < n$。位置$i$的贡献次数$nums[i]$为$(i+1) \times (n-i)$。最小的贡献即为排序后的每个数乘以对应的贡献次数：