Gowthaman Ravi
Gowthy's Blog

Gowthy's Blog

Maximum Erasure Value | Leetcode

Gowthaman Ravi's photo
Gowthaman Ravi
·Jun 13, 2022·

Subscribe to my newsletter and never miss my upcoming articles

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

public class maximumErasureValue {

//Approach-1 - SImple two pointer
    public static int findMaximumErasureValueUsingSimpleTwoPointer(int[] nums){
        int maxScore = 0, currScore = 0;
        Set<Integer> set = new HashSet<Integer>();
        for(int left =0, right=0; right< nums.length; right++) {

            while(!set.add(nums[right])) {
                currScore -= nums[left];
                set.remove(nums[left++]);
            }
            currScore += nums[right];
            maxScore = Math.max(currScore,maxScore);
        }
        return maxScore;
    }

//Approach-2 - Prefix Sum with two pointer
    public static int findMaximumErasureValueUsingPrefixSum(int[] nums){
        int maxScore = 0, currScore =0;
        Map<Integer, Integer> lastIndex = new HashMap<>();
        int[] prefixSum = new int[nums.length+1];
        for(int left=0, right=0; right<nums.length; right++){
            prefixSum[right+1]= prefixSum[right] + nums[right];
            if(lastIndex.containsKey(nums[right])) {
                left = Math.max(left, lastIndex.get(nums[right]) + 1);
            }
            currScore = prefixSum[right+1]-prefixSum[left];
            maxScore = Math.max(maxScore, currScore);
            lastIndex.put(nums[right],right);
        }
        return maxScore;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,2,1,2,5,2,1,2,5};
        System.out.println(" Maximum Erasure Value - Two Pointer: "+ findMaximumErasureValueUsingSimpleTwoPointer(nums));
        System.out.println(" Maximum Erasure Value - Prefix Sum : "+ findMaximumErasureValueUsingPrefixSum(nums));
    }
}
 
Share this