方法一：贪心 + 哈希表

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

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

###python

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

###java

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;
    }
}

###cpp

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;
    }
};

###go

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
}

###ts

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;
}

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

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

方法一：对正数去重

思路

题目其实是要求找到一个非空子序列，并且元素不能重复，求最大和。我们可以贪心地、不重复地将所有正数放入一个哈希集合并求和。如果该哈希集合内不存在任何整数，则返回数组中元素的最大值。

代码

###Python

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        positiveNumsSet = set([num for num in nums if num > 0])
        return max(nums) if len(positiveNumsSet) == 0 else sum(positiveNumsSet)

###C++

class Solution {
public:
    int maxSum(vector<int>& nums) {
        unordered_set<int> positiveNumsSet;
        for (int num : nums) {
            if (num > 0) {
                positiveNumsSet.emplace(num);
            }
        }
        if (positiveNumsSet.empty()) {
            return *max_element(nums.begin(), nums.end());
        }
        return accumulate(positiveNumsSet.begin(), positiveNumsSet.end(), 0);
    }
};

###Java

class Solution {
    public int maxSum(int[] nums) {
        Set<Integer> positiveNumsSet = new HashSet<>();
        for (int num : nums) {
            if (num > 0) {
                positiveNumsSet.add(num);
            }
        }
        if (positiveNumsSet.isEmpty()) {
            return Arrays.stream(nums).max().getAsInt();
        }
        return positiveNumsSet.stream().mapToInt(Integer::intValue).sum();
    }
}

###C#

public class Solution {
    public int MaxSum(int[] nums) {
        HashSet<int> positiveNumsSet = new HashSet<int>();
        foreach (int num in nums) {
            if (num > 0) {
                positiveNumsSet.Add(num);
            }
        }
        if (positiveNumsSet.Count == 0) {
            return nums.Max();
        }
        return positiveNumsSet.Sum();
    }
}

###Go

func maxSum(nums []int) int {
    positiveNumsSet := make(map[int]bool)
    maxNum := nums[0]
    for _, num := range nums {
        if num > 0 {
            positiveNumsSet[num] = true
        }
        maxNum = max(maxNum, num)
    }
    
    if len(positiveNumsSet) == 0 {
        return maxNum
    }
    sum := 0
    for num := range positiveNumsSet {
        sum += num
    }
    return sum
}

###C

typedef struct {
    int key;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, int key) {
    HashItem *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, int key) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    HASH_ADD_INT(*obj, key, pEntry);
    return true;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr);
    }
}

int maxSum(int* nums, int numsSize) {
    HashItem *positiveNumsSet = NULL;
    int maxNum = nums[0];
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > 0) {
            hashAddItem(&positiveNumsSet, nums[i]);
        }
        maxNum = fmax(maxNum, nums[i]);
    }
    if (HASH_COUNT(positiveNumsSet) == 0) {
        hashFree(&positiveNumsSet);
        return maxNum;
    }
    int sum = 0;
    for (HashItem *pEntry = positiveNumsSet; pEntry; pEntry = pEntry->hh.next) {
        sum += pEntry->key;
    }
    hashFree(&positiveNumsSet);
    return sum;
}

###JavaScript

var maxSum = function(nums) {
    const positiveNumsSet = new Set(nums.filter(num => num > 0));
    return positiveNumsSet.size === 0 ? Math.max(...nums) : [...positiveNumsSet].reduce((a, b) => a + b, 0);
};

###TypeScript

function maxSum(nums: number[]): number {
    const positiveNumsSet = new Set(nums.filter(num => num > 0));
    return positiveNumsSet.size === 0 ? Math.max(...nums) : [...positiveNumsSet].reduce((a, b) => a + b, 0);
};

###Rust

use std::collections::HashSet;

impl Solution {
    pub fn max_sum(nums: Vec<i32>) -> i32 {
        let positive_nums_set: HashSet<i32> = nums.iter().filter(|&&x| x > 0).cloned().collect();
        if positive_nums_set.is_empty() {
            *nums.iter().max().unwrap()
        } else {
            positive_nums_set.iter().sum()
        }
    }
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。

• 空间复杂度：$O(n)$。