Two Pointers for a Linear Solution IV

I've written before about two-pointers techniques before. In this particular case (Medium LC), you'll need to use some sort of hash or memo to keep track of all the unique values, but the two-pointers solution remains standard. Here it is: Maximum Erasure Value - LeetCode

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

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 = [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 <= 105
• 1 <= nums[i] <= 104

Accepted

3,679

Submissions

8,274

Given the 10^5 constraint, certainly you'll want to go with either O(N) (preferably) or O(NLogN), but not with N^2 (10^10, intractable). Keep two pointers, one the "left" and the other one the "right". Only move the right if the element is unique. Otherwise, move the left. Keep track of the current sum, and whenever the current sum increments, check it against the max. Should do it. Cheers and happy holidays! ACC.

public int MaximumUniqueSubarray(int[] nums)
{
    Hashtable unique = new Hashtable();

    int left = 0;
    int right = 0;
    int max = 0;
    int current = 0;

    while (right < nums.Length)
    {
        if (!unique.ContainsKey(nums[right]))
        {
            current += nums[right];
            max = Math.Max(max, current);
            unique.Add(nums[right], true);
            right++;
        }
        else
        {
            unique.Remove(nums[left]);
            current -= nums[left];
            left++;
        }
    }

    return max;
}