学妹昨晚参加了B站的2022届秋招算法笔试，做完给我发来了一道题，想考考我，说挺难的。
我看了两分钟，给她发去了我的思路。然后学妹一眼就看懂了，立马秒过。
那么这道题到底是怎么做的呢？
题目要求将个数切分成块，求每块的序号乘上该块内数字之和的最大值。
那么首先我们可以用来表示前缀和，也就是。
然后假设个子序列中，第个子序列的末尾元素为，其中。那么第个子序列的元素和就可以用前缀和来表示为。
然后题目要求的最大值就可以表示为：
展开并化简就可以得到：
后面一项就是整个数组之和的倍，是一个定值。所以要求这个式子的最大值，就是求的最小值。
又因为，所以就是求的最小值。
可以发现，这个前缀和其实是互不干扰的，所以只需要对所有的前缀和进行排序，取最小的个就行了。
C++代码如下：
#include <stdio.h> #include <algorithm> using namespace std; typedef long long ll; const int N = 300010; ll a[N]; int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 0; i < n; ++i) { scanf("%lld", &a[i]); if (i) a[i] += a[i-1]; } sort(a, a+n-1); ll res = 0; for (int i = 0; i < k-1; ++i) res += a[i]; res = -res + k * a[n-1]; printf("%lld\n", res); return 0; }
Python代码：
n, k = [int(x) for x in input().strip().split(" ")] a = [int(x) for x in input().strip().split(" ")] S = [sum(a[:i+1]) for i in range(n-1)] S.sort() res = -sum(S[:k-1]) + k * sum(a) print(res)
