题意

给定一个长度为 $n$ 的 $a$ 数组，将其划分成 $k$ 个非空连续子段，子段和定义为该子段中所有元素之和，求子段和的最大极差。
极差指最大值与最小值之差。

思路

观察发现，$a$ 数组里都是非负整数，易知，最佳情况一定形如：

• 一个仅由一个元素形成的子段提供最小值。

因为假如最小值是由多个元素形成的子段和，则删除其中的元素一定会使子段和变小或不变，且有可能使最大值增大，故使元素个数减到最小值 $1$ 一定不劣，可以确认不可能更优。

• 在剩下的元素中，由极大子段提供最大值。

设极大子段长度为 $L$。
极大子段 要满足两个条件：

1. 使得数组能够划分为 $k$ 个非空连续子段，${n-L} \ge {k-1}$，移项得 $L\le {n-k+1}$。假如 $L$ 超出该范围，剩下就算全是一个仅由一个元素形成的子段，其数目也到不了 $k$，而取到 $n-k+1$ 则刚刚好。
2. 但也不是所有情况都能取到 $n-k+1$ 的长度，假设选定的最小值子段中元素的下标为 $i$，则 $L$ 不能超出 $i$ 前后剩下的最大长度。例如 $n=6$，$k=3$，$i=2$，此时满足条件1的最大长度 $n-k+1=4$，而仅有第一个元素的子段长度为 $1$，也算一个极大子段。

于是，我们就可以这么处理：枚举每一个位置 $i$ 为最小值子段的情况。对于每种情况，如果 $i$ 前面或后面长度不到条件1的限制，则求出这一整段的和（预处理出前缀和解决）；否则把该区间中所有长度为 $n-k+1$ 的子段和最大值求出来（预处理出 st 表解决）。这样我们就得到了极大子段和的最大值。最终答案就是所有情况的 $\max$。

你以为这样就结束了吗？
我一开始也是这么以为的，然而没过。
原来当 $k=2$ 时，如果取了中间的某个点，就至少有 $3$ 段了，不符合条件，于是应该对于 $k=2$ 的情况进行特判，其答案为 $\max$(分成 $a_1$ 和剩下部分的答案，分成 $a_n$ 和剩下部分的答案)。
再手推一下，发现 $k > 2$ 时都满足一般情况，不需要其他特判了。
这样就可以过了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
int n,m,k,lg[N];
ll a[N],pre[N],lst[N],ans,tmp;
ll st[N][20];
void bd_st(){
	for(int i=1;i<=m;i++)st[i][0]=pre[i+k-1]-pre[i-1];
	int l=lg[m];
	for(int j=1;j<=l;j++){
		for(int i=1;i<=m-(1<<j)+1;i++){
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
ll gt_ma(int l,int r){
	r=r-k+1;
	int L=lg[r-l+1];
	return max(st[l][L],st[r-(1<<L)+1][L]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	if(k==2){
		for(int i=1;i<=n;i++){
			cin>>a[i];
			tmp+=a[i];
		}
		cout<<max(abs(tmp-2*a[1]),abs(tmp-2*a[n]));
		return 0;
	} 
	k=n-k+1;
	m=n-k+1;
	for(int i=2;i<=m;i++)lg[i]=lg[i-1]+(i==(1<<(lg[i-1]+1)));
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
	for(int i=n;i>=m;i--)lst[i]=lst[i+1]+a[i];
	bd_st();
	for(int i=1;i<=n;i++){
		tmp=0;
		if(i<=k)tmp=max(tmp,pre[i-1]);
		else tmp=max(tmp,gt_ma(1,i-1));
		if(i>=m)tmp=max(tmp,lst[i+1]);
		else tmp=max(tmp,gt_ma(i+1,n));
		tmp-=a[i];
		ans=max(ans,tmp);
	}
	cout<<ans;
	return 0;
}

翻了下已有的题解，都是 $O(n)$ 做法的大佬，而我预处理了一个 st 表，复杂度还多了个 $\log$，不够优秀。由于我用 st 表求的最大值，范围要么从头开始，要么到最后，所以其实完全可以处理出长度为 $n-k+1$ 的子段和前后缀最大值。如果这题数据范围再大些，我的解法就会被卡。

后记

我必须承认，自己的水平实在不高。但我享受写题解的过程，这是一种思想的传递，表达能力的锻炼。
这篇题解写的不是最优解法，但我希望带给大家的帮助不仅是一个解法，更是一个进步的过程。在写题时，发现自己的不足，以及可优化的地方，搞懂优化的原理，这就是一种成长。
如有意见和建议欢迎指出，大家的提议是我进步的动力。感谢所有支持我的人，谢谢你们！