Question

1695. Maximum Erasure Value

中文文档

Description

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

Solutions

Solution 1: Array or Hash Table + Prefix Sum

We use an array or hash table $d$ to record the last occurrence of each number, use $s$ to record the prefix sum, and use $j$ to record the left endpoint of the current non-repeating subarray.

We traverse the array, for each number $v$, if $d[v]$ exists, then we update $j$ to $max(j, d[v])$, which ensures that the current non-repeating subarray does not contain $v$. Then we update the answer to $max(ans, s[i] - s[j])$, and finally update $d[v]$ to $i$.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $nums$.

class Solution:
  def maximumUniqueSubarray(self, nums: List[int]) -> int:
    d = defaultdict(int)
    s = list(accumulate(nums, initial=0))
    ans = j = 0
    for i, v in enumerate(nums, 1):
      j = max(j, d[v])
      ans = max(ans, s[i] - s[j])
      d[v] = i
    return ans

class Solution {
  public int maximumUniqueSubarray(int[] nums) {
    int[] d = new int[10001];
    int n = nums.length;
    int[] s = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = 0, j = 0;
    for (int i = 1; i <= n; ++i) {
      int v = nums[i - 1];
      j = Math.max(j, d[v]);
      ans = Math.max(ans, s[i] - s[j]);
      d[v] = i;
    }
    return ans;
  }
}

class Solution {
public:
  int maximumUniqueSubarray(vector<int>& nums) {
    int d[10001]{};
    int n = nums.size();
    int s[n + 1];
    s[0] = 0;
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = 0, j = 0;
    for (int i = 1; i <= n; ++i) {
      int v = nums[i - 1];
      j = max(j, d[v]);
      ans = max(ans, s[i] - s[j]);
      d[v] = i;
    }
    return ans;
  }
};

func maximumUniqueSubarray(nums []int) (ans int) {
  d := [10001]int{}
  n := len(nums)
  s := make([]int, n+1)
  for i, v := range nums {
    s[i+1] = s[i] + v
  }
  for i, j := 1, 0; i <= n; i++ {
    v := nums[i-1]
    j = max(j, d[v])
    ans = max(ans, s[i]-s[j])
    d[v] = i
  }
  return
}

function maximumUniqueSubarray(nums: number[]): number {
  const m = Math.max(...nums);
  const n = nums.length;
  const s: number[] = Array.from({ length: n + 1 }, () => 0);
  for (let i = 1; i <= n; ++i) {
    s[i] = s[i - 1] + nums[i - 1];
  }
  const d = Array.from({ length: m + 1 }, () => 0);
  let [ans, j] = [0, 0];
  for (let i = 1; i <= n; ++i) {
    j = Math.max(j, d[nums[i - 1]]);
    ans = Math.max(ans, s[i] - s[j]);
    d[nums[i - 1]] = i;
  }
  return ans;
}