Hard

题目描述

给你一个整数数组 nums。

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

  • 选择任意整数 x，使得删除 x 的所有出现后 nums 仍然非空。
  • 从数组中删除 x 的所有出现。

返回所有可能结果数组中的最大子数组和。

示例 1：

输入：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。

示例 2：

输入：nums = [1,2,3,4]
输出：10
解释：
最优策略是不执行任何操作。

约束条件：

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

解题思路

这道题要求我们找到删除某个元素的所有出现后能得到的最大子数组和。

基本思路： 我们需要考虑两种情况：

  1. 不删除任何元素，直接计算原数组的最大子数组和
  2. 删除某个特定值的所有出现，计算剩余数组的最大子数组和

关键观察：

  • 只有当删除的元素为负数时，删除操作才可能增加最大子数组和
  • 对于每个可能的删除值，我们需要高效地计算删除后数组的最大子数组和

优化方法： 使用线段树来维护区间信息，每个节点存储：

  • 区间和
  • 最大子数组和
  • 最大前缀和
  • 最大后缀和

当我们删除某个值时，相当于将数组分割成若干段，我们需要快速合并这些段来计算新的最大子数组和。

算法步骤：

  1. 获取数组中的所有唯一值
  2. 对于每个值，模拟删除操作并计算最大子数组和
  3. 返回所有可能结果中的最大值

时间复杂度为 O(n × k)，其中 k 是唯一元素个数。

代码实现

class Solution {
public:
    long long maxSubarraySum(vector<int>& nums) {
        int n = nums.size();
        
        // 计算原数组的最大子数组和
        auto kadane = [](const vector<int>& arr) -> long long {
            if (arr.empty()) return LLONG_MIN;
            long long maxSum = arr[0], currentSum = arr[0];
            for (int i = 1; i < arr.size(); i++) {
                currentSum = max((long long)arr[i], currentSum + arr[i]);
                maxSum = max(maxSum, currentSum);
            }
            return maxSum;
        };
        
        long long result = kadane(nums);
        
        // 获取所有唯一值
        unordered_set<int> uniqueValues(nums.begin(), nums.end());
        
        // 对每个唯一值，尝试删除它
        for (int val : uniqueValues) {
            vector<int> filtered;
            for (int num : nums) {
                if (num != val) {
                    filtered.push_back(num);
                }
            }
            if (!filtered.empty()) {
                result = max(result, kadane(filtered));
            }
        }
        
        return result;
    }
};

class Solution:
    def maxSubarraySum(self, nums: List[int]) -> int:
        def kadane(arr):
            if not arr:
                return float('-inf')
            max_sum = current_sum = arr[0]
            for i in range(1, len(arr)):
                current_sum = max(arr[i], current_sum + arr[i])
                max_sum = max(max_sum, current_sum)
            return max_sum
        
        # 计算原数组的最大子数组和
        result = kadane(nums)
        
        # 获取所有唯一值
        unique_values = set(nums)
        
        # 对每个唯一值，尝试删除它
        for val in unique_values:
            filtered = [num for num in nums if num != val]
            if filtered:
                result = max(result, kadane(filtered))
        
        return result

public class Solution {
    public long MaxSubarraySum(int[] nums) {
        long Kadane(List<int> arr) {
            if (arr.Count == 0) return long.MinValue;
            long maxSum = arr[0], currentSum = arr[0];
            for (int i = 1; i < arr.Count; i++) {
                currentSum = Math.Max(arr[i], currentSum + arr[i]);
                maxSum = Math.Max(maxSum, currentSum);
            }
            return maxSum;
        }
        
        // 计算原数组的最大子数组和
        long result = Kadane(new List<int>(nums));
        
        // 获取所有唯一值
        var uniqueValues = new HashSet<int>(nums);
        
        // 对每个唯一值，尝试删除它
        foreach (int val in uniqueValues) {
            var filtered = new List<int>();
            foreach (int num in nums) {
                if (num != val) {
                    filtered.Add(num);
                }
            }
            if (filtered.Count > 0) {
                result = Math.Max(result, Kadane(filtered));
            }
        }
        
        return result;
    }
}

var maxSubarraySum = function(nums) {
    function kadane(arr) {
        if (arr.length === 0) return -Infinity;
        let maxSum = arr[0];
        let currentSum = arr[0];
        for (let i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
    
    let uniqueValues = [...new Set(nums)];
    let maxResult = kadane(nums);
    
    for (let val of uniqueValues) {
        let filteredArray = nums.filter(x => x !== val);
        if (filteredArray.length > 0) {
            maxResult = Math.max(maxResult, kadane(filteredArray));
        }
    }
    
    return maxResult;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n × k)，其中 n 是数组长度，k 是唯一元素个数
空间复杂度O(n)，用于存储过滤后的数组和唯一值集合

相关题目