题目描述

给你一个整数数组 nums。

你可以对数组执行以下操作 至多 一次：

• 选择 nums 中存在的 任意 整数 X，确保删除所有值为 X 的元素后剩下数组 非空。
• 将数组中 所有 值为 X 的元素都删除。

请你返回 所有 可能得到的数组中 最大 子数组和为多少。

子数组 指的是一个数组中一段连续 非空 的元素序列。

样例

输入：nums = [-3,2,-2,-1,3,-2,3]

输出：7

解释：

我们执行至多一次操作后可以得到以下数组：

原数组是 nums = [-3, 2, -2, -1, 3, -2, 3]。最大子数组和为 3 + (-2) + 3 = 4。
删除所有 X = -3 后得到 nums = [2, -2, -1, 3, -2, 3]。最大子数组和为 3 + (-2) + 3 = 4。
删除所有 X = -2 后得到 nums = [-3, 2, -1, 3, 3]。最大子数组和为 2 + (-1) + 3 + 3 = 7。
删除所有 X = -1 后得到 nums = [-3, 2, -2, 3, -2, 3]。最大子数组和为 3 + (-2) + 3 = 4。
删除所有 X = 3 后得到 nums = [-3, 2, -2, -1, -2]。最大子数组和为 2。
输出为 max(4, 4, 7, 4, 2) = 7。

输入：nums = [1,2,3,4]

输出：10

解释：

最优操作是不删除任何元素。

限制

• 1 <= nums.length <= 10^5
• -10^6 <= nums[i] <= 10^6

算法

(线段树) $O(n \log n)$

1. 用线段树维护最大子数组的和。
2. 如果初始的最大子数组小于等于 0，则答案就是数组中最大的数字。
3. 删除的数字一定为负数，每次删除考虑将删除位置都变为 $0$，用线段树维护整个数组的最大子数组的和，更新答案。

时间复杂度

• 建树的时间复杂度为 $O(n)$。
• 每次单点更新的时间复杂度为 $O(\log n)$，最多更新 $O(n)$ 次。
• 查询的时间复杂度为常数。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储线段树。

C++ 代码

#define LL long long

const int N = 100010;

struct Node {
    LL ls, rs, s, mx;
    Node() {}
    Node(LL ls_, LL rs_, LL s_, LL mx_) {
        ls = ls_; rs = rs_; s = s_; mx = mx_;
    }
};

class Solution {
private:
    Node nodes[N << 2];

    void pushup(int rt) {
        int lson = rt << 1, rson = rt << 1 | 1;
        nodes[rt].ls = max(nodes[lson].ls, nodes[lson].s + nodes[rson].ls);
        nodes[rt].rs = max(nodes[rson].rs, nodes[rson].s + nodes[lson].rs);
        nodes[rt].s = nodes[lson].s + nodes[rson].s;
        nodes[rt].mx = max(
            max(nodes[lson].mx, nodes[rson].mx),
            nodes[lson].rs + nodes[rson].ls
        );
    }

    void build(int l, int r, int rt, const vector<int> &nums) {
        if (l == r) {
            nodes[rt] = Node(nums[l], nums[l], nums[l], nums[l]);

            return;
        }

        int mid = (l + r) >> 1;
        build(l, mid, rt << 1, nums);
        build(mid + 1, r, rt << 1 | 1, nums);
        pushup(rt);
    }

    void update(int p, int x, int l, int r, int rt) {
        if (l == r) {
            nodes[rt] = Node(x, x, x, x);
            return;
        }

        int mid = (l + r) >> 1;
        if (p <= mid) update(p, x, l, mid, rt << 1);
        else update(p, x, mid + 1, r, rt << 1 | 1);

        pushup(rt);
    }

public:
    LL maxSubarraySum(vector<int>& nums) {
        const int n = nums.size();

        unordered_map<int, vector<int>> h;
        int mx = INT_MIN;
        for (int i = 0; i < n; i++) {
            mx = max(mx, nums[i]);
            h[nums[i]].push_back(i);
        }

        build(0, n - 1, 1, nums);
        LL ans = nodes[1].mx;

        if (ans <= 0)
            return mx;

        if (h.size() == 1)
            return ans;

        for (const auto &[x, v] : h) {
            if (x >= 0)
                continue;

            for (int p : v)
                update(p, 0, 0, n - 1, 1);

            ans = max(ans, nodes[1].mx);

            for (int p : v)
                update(p, x, 0, n - 1, 1);
        }

        return ans;
    }
};