【拼多多】20250309笔试真题第2题记录

一开始想到的是用DP解，没成功，后来又用了前缀和/后缀和也不对

我去网上找题解，看到了一个不错的题解，代码量不大，但是相应的解释太少了，我就自己琢磨

好歹也是把思路理清了，附上代码

菜就多练

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char const* argv[]) {
    // 5
    // 1 -4 10 -30 2
    // prefix = {1, -3, 7, -23, -21}
    // min_prefix = {1, -3, -3, -23, -23}
    // max_prefix = {1, 1, 7, 7, 7}
    long long ans = 0;
    int n = 0;
    cin >> n;
    vector<int> step(n);
    vector<long long> prefix(n + 1);
    vector<long long> min_prefix(n + 1);
    vector<long long> max_prefix(n + 1);
    // 不使用传送门, ans = max(abs(prefix[i])) 即prefix[]数组元素绝对值的最大值
    // 使用传送门, 假设在 i 处使用了传送门, 在 j 处到达了了最远位置, 可以表示为
    // -prefix[i] + (prefix[j] - prefix[i]), 其中(prefix[j] - prefix[i])表示step[i...j]的区间和
    // -prefix[i] + (prefix[j] - prefix[i]) = prefix[j] - 2*prefix[i]
    // 那么距离为 abs(prefix[j] - 2*prefix[i]), 这里有限制条件(j > i), 问题转化为求这个表达式的最大值
    // 暴力遍历会超时, 优化一下怎么求最大值
    // 在一次遍历中, prefix[k]是确定的
    // 数学表达式 |a - b| = |b - a|, 固定 a 不变, 当 b 取最大或最小值时可以使得 |a - b|最大
    // 由于 j > i, 相当于求在 j 位置之前的最小/最大前缀和
    // 也就是[1, j]区间上最小/最大的前缀和, 注意这里的 j 不是固定的, 而是会变化的
    // 所以可以遍历prefix[]数组, 随着 j 的位置变化, 最小/最大前缀和会变, 需要 2 个数组来维护
    for (int i = 1; i <= n; i++) {
        cin >> step[i];
        prefix[i] = prefix[i - 1] + step[i];
        ans = max(ans, abs(prefix[i]));
        if (i == 1) {
            min_prefix[i] = max_prefix[i] = prefix[i];
        }
        else {
            min_prefix[i] = min(min_prefix[i - 1], prefix[i]);
            max_prefix[i] = max(max_prefix[i - 1], prefix[i]);
        }
    }
    // 按顺序走传送门
    for (int i = 1; i <= n; i++) {
        long long max1 = abs(prefix[i] - 2*min_prefix[i]);
        long long max2 = abs(prefix[i] - 2*max_prefix[i]);
        ans = max(ans, max(max1, max2));
    }
    cout << ans << endl;
    // system("pause");
    return 0;
}