1695. Maximum Erasure Value

[mah-shamim]

Topics: Array, Hash Table, Sliding Window, Weekly Contest 220

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

Hint:

1. The main point here is for the subarray to contain unique elements for each index. Only the first subarrays starting from that index have unique elements.
2. This can be solved using the two pointers technique

[mah-shamim]

We need to find the maximum sum of a contiguous subarray where all elements are unique. The solution involves efficiently scanning the array while maintaining a sliding window that ensures all elements within the window are distinct.

Approach

1. Sliding Window Technique: We use two pointers, left and right, to represent the current window of elements. The right pointer expands the window by including new elements, while the left pointer contracts the window when a duplicate element is encountered.
2. Frequency Tracking: A frequency array keeps track of the count of each element within the current window. This helps in quickly identifying duplicates.
3. Sum Maintenance: As we expand the window by moving the right pointer, we add the current element to a running sum. If adding an element causes a duplicate (its frequency exceeds 1), we move the left pointer to the right, subtracting elements from the running sum until the duplicate is removed.
4. Max Sum Update: After ensuring all elements in the current window are unique, we compare the running sum with the maximum sum encountered so far and update it if necessary.

This approach efficiently processes the array in O(n) time with O(1) space for the frequency array (since the maximum value of elements is constrained to 104).

Let's implement this solution in PHP: 1695. Maximum Erasure Value

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function maximumUniqueSubarray($nums) {
    $n = count($nums);
    $max_sum = 0;
    $current_sum = 0;
    $freq = array_fill(0, 10001, 0);
    $left = 0;

    for ($right = 0; $right < $n; $right++) {
        $num = $nums[$right];
        $current_sum += $num;
        $freq[$num]++;

        while ($freq[$num] > 1) {
            $left_num = $nums[$left];
            $current_sum -= $left_num;
            $freq[$left_num]--;
            $left++;
        }

        if ($current_sum > $max_sum) {
            $max_sum = $current_sum;
        }
    }

    return $max_sum;
}

// Test cases
$nums1 = array(4, 2, 4, 5, 6);
echo maximumUniqueSubarray($nums1) . "\n"; // Output: 17

$nums2 = array(5, 2, 1, 2, 5, 2, 1, 2, 5);
echo maximumUniqueSubarray($nums2) . "\n"; // Output: 8
?>

Explanation:

1. Initialization: We start by initializing variables to keep track of the maximum sum ($max_sum), the current sum of the window ($current_sum), and a frequency array ($freq) to count occurrences of each number in the current window. The $left pointer starts at 0.
2. Expanding the Window: For each element (using the $right pointer), we add the element to $current_sum and increment its count in $freq.
3. Handling Duplicates: If the count of the current element exceeds 1, we move the $left pointer to the right, subtracting elements from $current_sum and decrementing their counts in $freq until the current element's count drops to 1.
4. Updating Maximum Sum: After ensuring all elements in the window are unique, we compare $current_sum with $max_sum and update $max_sum if necessary.
5. Result: After processing all elements, $max_sum holds the maximum sum of any contiguous subarray with all unique elements, which is returned as the result.

This approach efficiently processes the array in linear time, making it optimal for large input sizes as specified in the problem constraints.

[topugit]

Thanks for solving the problem of "Maximum Erasure Value"

[mah-shamim]

Thanks