Leetcode 1695. How To Find The Maximal Subarray Having Distinct Elements

High-scoring subarrays with distinct elements tracked efficiently using sliding window and prefix sums in C++.

Problem statement

You have an array of positive integers called nums, and you wish to remove a subarray from it that consists of distinct elements. The score you achieve by removing this subarray is the sum of its elements.

Your goal is to determine the highest possible score attainable by erasing exactly one subarray from the provided array.

A subarray, denoted as b, is considered part of another array, a, if it appears consecutively within a, i.e., if it is equivalent to a[l], a[l+1], ..., a[r] for some indices (l, r).

Example 1

Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].

Example 2

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The optimal subarray here is [5,2,1] or [1,2,5].

Constraints

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

Solution: Store the position of the visited elements

You can use a map to store the position of the elements of nums. Then when iterating nums you can identify if an element has been visited before. That helps you to decide if a subarray contains unique elements.

Code

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int maximumUniqueSubarray(vector<int>& nums) {
    vector<int> sum(nums.size(), 0);
    sum[0] = nums.at(0);
    int maxSum = sum.at(0);
    unordered_map<int, int> position;
    position[nums.at(0)] = 0;
    int start = -1;
    for (int i = 1; i < nums.size(); i++) {
        sum[i] = sum.at(i - 1) + nums.at(i);
        auto it = position.find(nums.at(i));
        if (it != position.end()) {
            start = max(start, it->second);
            it->second = i;
        } else {
            position.insert({nums.at(i), i});
        }            
        if (start == -1) {
            maxSum = sum.at(i);
        } else {
            maxSum = max(maxSum, sum.at(i) - sum.at(start));
        }
    }
    return maxSum;
}
int main() {
    vector<int> nums{4,2,4,5,6};
    cout << maximumUniqueSubarray(nums) << endl;
    nums = {5,2,1,2,5,2,1,2,5};
    cout << maximumUniqueSubarray(nums) << endl;
}

Output:
17
8

Code explanation

This C++ code defines a function maximumUniqueSubarray that finds the maximum sum of a subarray in the given vector nums with the constraint that all elements must be unique. It uses two key techniques: prefix sums and a sliding window approach.

Here's a step-by-step explanation of how the code works:

1. The code initializes a vector called sum of the same size as the input nums. sum is used to store the cumulative sums of elements in nums, where sum[i] represents the sum of the first i elements of nums. The initial value of sum[0] is set to nums[0].
2. It initializes the maxSum variable to the value of sum[0], which represents the maximum sum found so far.
3. An unordered map position is created to store the position (index) of each element in nums. This map keeps track of the most recent position where each element was encountered.
4. The initial position of the first element, nums[0], is set to 0 in the position map.
5. The variable start is initialized to -1, which will be used to keep track of the starting index of the subarray with unique elements.
6. The code enters a loop that iterates for each element in nums except the first one.
7. The sum vector is updated with the cumulative sum up to the current element nums[i]. This is done to calculate the sum of any subarray later efficiently.
8. Inside the loop, the code checks if the current element nums[i] is already in the position map. If nums[i] is found in the position map, it means that this element has been encountered before. In this case, the code updates the start variable to be the maximum of its current value and the position of nums[i] from the position map. This sliding window technique ensures that the subarray only contains unique elements.
9. The current position of nums[i] is updated in the position map.
10. The code calculates the maximum sum using the sliding window approach. If start is still equal to -1, it means that all elements up to nums[i] are unique, so the maximum sum is simply sum[i]. Otherwise, the code calculates the maximum of the current maxSum and the sum of the elements between the current position i and the start position. This ensures that the subarray contains unique elements.
11. Finally, the function returns maxSum, which contains the maximum sum of a subarray with unique elements.

Complexity

This solution efficiently finds the maximum sum of a subarray with unique elements using a sliding window approach and prefix sums.

• Runtime: O(N), where N = nums.length.
• Extra space: O(N).

Thanks for reading!

I hope you enjoyed this content. Don't keep it to yourself! Share it with your network and help each other improve your coding skills and advance your career!

Nhut Nguyen, the author of The Problem Solver's Guide To Coding.