Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Deleting arbitrary elements lets any retained subsequence become contiguous. To maximize a unique subarray's sum, keep one copy of every positive value and avoid negative values. However, the result must be nonempty, so if there are no positive values we must still keep the largest element.

Approach

Build the set of distinct input values. Initialize the answer with its maximum value and remove that value from the set, ensuring a nonempty selection from the start. For each remaining distinct value, choose the larger of the current total and the total plus that value.

This adds every remaining positive value and skips negative ones; zeros do not change the sum. Duplicate occurrences cannot contribute because the selected subarray must contain distinct values. Any selected values can be retained in their original order while deleting intervening elements, so the computed sum is achievable.

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        n = len(nums)
        all = set(nums)
        mx = max(all)
        all.remove(mx)
        res = mx

        for v in all:
            res = max(res, res + v)

        return res

Complexity analysis

Let n = nums.length and u be the number of distinct values. Time: O(n + u). Auxiliary space: O(u).