本题把 $k$ 也变成 $10^5$ 上限一样可以做。

已知股票买卖会在一定阶段上交易次数越多获利越大，但是到了一定程度就会不得不高买低卖导致负收益。设可以必须完成买卖 $k$ 次带来的最大收益是 $f(k)$ ，则 $(k,f(k))$ 的图像构成一个上凸壳。所以可以使用 wqs 二分。

结合 AcWing 1059. 股票买卖 6 每一次买卖包含手续费 $c$ 的特性做线性 DP，设 $f_{i,0/1}$ 是第 $i$ 天不持股/持股状态的最大获利，那么线性 DP 不难求解。wqs 二分就相当于我们对 $c$ 做二分，然后再不考虑买卖次数限制的条件下跑线性 DP。

每次线性 DP 我们需要获利尽可能大， 同时交易次数尽可能少。对应上凸壳图像当中，出现多点共线的情况，需要有限取靠左的点。所以我们在 DP 的同时还要记录完整完成交易的次数。

对 $c$ 二分，找到能使交易次数 $\le k$ 的最小 $c$ 即可（已知 $c$ 单调增的情况下，最优解交易次数一定是单调减的），所以二分答案是使用 lower_bound 的形式搜索。

最终答案就是找到的 $c$ 下跑无限制的最大获利值加上 $k\times c$ 。

时间复杂度仅和 $c$ 二分查找的上界有关，与 $k$ 无关，为 $O(n\log V)$ 。

const int N = 100010;
int n, k;
int a[N];
struct dp_info
{
    int val, seg;
    dp_info(int d = 0, int s = 0) : val(d), seg(s) {}
    bool operator==(const dp_info& o) const { return (val == o.val) && (seg == o.seg); }
    bool operator>(const dp_info& o) const { return (val > o.val) || ((val == o.val) && (seg < o.seg)); }
    bool operator<(const dp_info& o) const { return !(((*this) == o) || ((*this) > o)); }
};
dp_info f[N][2]; 
dp_info solve(int c)
{
    f[1][0] = dp_info(0, 0), f[1][1] = dp_info(-a[1], 0);
    for (int i = 2; i <= n; ++i)
    {
        f[i][0] = std::max(f[i - 1][0], dp_info(f[i - 1][1].val + a[i] - c, f[i - 1][1].seg + 1));
        f[i][1] = std::max(f[i - 1][1], dp_info(f[i - 1][0].val - a[i], f[i - 1][0].seg));
    }
    return std::max(f[n][0], f[n][1]);
}
signed main()
{
    while (rd(&n) && rd(&k))
    {
        for (int i = 1; i <= n; ++i)
            rd(&a[i]);
        int lo = 0, hi = 114514, mi = 0;
        while (lo < hi)
        {
            mi = (lo + hi) >> 1;
            (solve(mi).seg > k) ? (lo = mi + 1) : (hi = mi);
        }
        wr(solve(lo).val + lo * k), putchar('\n');
    }
}