3487. 删除后的最大子数组元素和

题目描述

给你一个整数数组 nums 。

你可以从数组 nums 中删除任意数量的元素，但不能将其变为空数组。执行删除操作后，选出 nums 中满足下述条件的一个子数组：

子数组中的所有元素 互不相同 。
最大化 子数组的元素和。

返回子数组的 最大元素和 。

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

示例 1：

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

输出：15

解释：

不删除任何元素，选中整个数组得到最大元素和。

示例 2：

输入：nums = [1,1,0,1,1]

输出：1

解释：

删除元素 nums[0] == 1、nums[1] == 1、nums[2] == 0 和 nums[3] == 1 。选中整个数组 [1] 得到最大元素和。

示例 3：

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

输出：3

解释：

删除元素 nums[2] == -1 和 nums[3] == -2 ，从 [1, 2, 1, 0, -1] 中选中子数组 [2, 1] 以获得最大元素和。

提示：

1 <= nums.length <= 100
-100 <= nums[i] <= 100

解法

方法一：贪心 + 哈希表

我们先找出数组中的最大值 \(\textit{mx}\)，如果 \(\textit{mx} \leq 0\)，那么数组中所有元素都小于等于 \(0\)，由于需要选出一个元素和最大的非空子数组，那么最大元素和就是 \(\textit{mx}\)。

如果 \(\textit{mx} > 0\)，那么我们需要找出数组中所有不同的正整数，并且这些正整数的和最大。我们可以使用一个哈希表 \(\textit{s}\) 来记录所有不同的正整数，然后遍历数组，将所有不同的正整数加起来即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{nums}\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        mx = max(nums)
        if mx <= 0:
            return mx
        ans = 0
        s = set()
        for x in nums:
            if x < 0 or x in s:
                continue
            ans += x
            s.add(x)
        return ans

class Solution {
    public int maxSum(int[] nums) {
        int mx = Arrays.stream(nums).max().getAsInt();
        if (mx <= 0) {
            return mx;
        }
        boolean[] s = new boolean[201];
        int ans = 0;
        for (int x : nums) {
            if (x < 0 || s[x]) {
                continue;
            }
            ans += x;
            s[x] = true;
        }
        return ans;
    }
}

class Solution {
public:
    int maxSum(vector<int>& nums) {
        int mx = ranges::max(nums);
        if (mx <= 0) {
            return mx;
        }
        unordered_set<int> s;
        int ans = 0;
        for (int x : nums) {
            if (x < 0 || s.contains(x)) {
                continue;
            }
            ans += x;
            s.insert(x);
        }
        return ans;
    }
};

func maxSum(nums []int) (ans int) {
    mx := slices.Max(nums)
    if mx <= 0 {
        return mx
    }
    s := make(map[int]bool)
    for _, x := range nums {
        if x < 0 || s[x] {
            continue
        }
        ans += x
        s[x] = true
    }
    return
}

function maxSum(nums: number[]): number {
    const mx = Math.max(...nums);
    if (mx <= 0) {
        return mx;
    }
    const s = new Set<number>();
    let ans: number = 0;
    for (const x of nums) {
        if (x < 0 || s.has(x)) {
            continue;
        }
        ans += x;
        s.add(x);
    }
    return ans;
}

3487. 删除后的最大子数组元素和

题目描述

解法

方法一：贪心 + 哈希表

评论