Find the Maximum Subarray Sum with Unique Values

You are given an array of positive integers. Find the maximum subarray sum with unique values.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

Example 1


Input	nums = [1, 2, 3, 5, 3, 1]
Output	10
Explanation	The subarray is [2, 3, 5] having maximum sum and unique values

Example 2


Input	nums = [1, 2, 3, 5, 3, 1, 4, 5, 1]
Output	10
Explanation	The subarray is [2, 3, 5] or [4, 5, 1] having maximum sum and unique values

Approach: Two Pointers

Like many subarray related problems, this can also be solved using two pointers.

Intuition

Let’s keep two pointers (left and right) both pointing to the start of the array. We will also be maintaining a hashmap to keep track of the unique elements considered in our solution.

As we iterate through our sliding window formed by the pointers left and right, we will increment the right pointer if it is not already in the solution subarray (sliding window). If it is present in the sliding window, we will increment the left pointer as long as nums[right] is present. The check of presence is computed using a hashmap which gives an $O(1)$ look-up time complexity.

The value of sum is also tracked and whenever we are incrementing the right pointer, we are adding nums[right] to the sum and whenever we are incrementing the left pointer, we are subtracting nums[left] from sum.

Implementation

In C++:

int maximumUniqueSubarray(vector<int>& nums) {
    unordered_set<int> unique;
    int left = 0, right = 0, sum = 0, ans = 0;
    while(right < nums.size()) {
        // if `nums[right]` is already in our solution subarray,
        // remove the `nums[left]` item and increment the left
        // pointer. Essentially, as long as nums[right] is there
        // in our solution subarray we will keep incrementing
        // the left pointer
        if (unique.count(nums[right])) {
            sum -= nums[left];
            unique.erase(nums[left]);
            ++left;
        // `nums[right]` is not in our solution subarray, include it
        } else {
            sum += nums[right];
            unique.insert(nums[right]);
            ans = max(ans, sum);
            ++right;
        }

    }
    return ans;
}

In Python:

def maximumUniqueSubarray(nums):
    unique = set()
    left, right, sum, ans = 0, 0, 0, 0
    while right < len(nums):
        # if `nums[right]` is already in our solution subarray,
        # remove the `nums[left]` item and increment the left
        # pointer. Essentially, as long as nums[right] is there
        # in our solution subarray we will keep incrementing
        # the left pointer
        if nums[right] in unique:
            sum -= nums[left]
            unique.remove(nums[left])
            left += 1
        # `nums[right]` is not in our solution subarray, include it
        else:
            sum += nums[right]
            unique.add(nums[right])
            ans = max(ans, sum)
            right += 1
    return ans

Complexity Analysis

Time Complexity: $O(N)$ where $N =$ size of the array
Space Complexity: $O(N)$ , in the worst case all the elements are unique, and we may have to store all of them in the hashmap

Published 29 May 2021

CS Posts on Twitter