[LeetCode] 1695. 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

Solution

3. Longest substring without repeating characters 的變形

這次不是要求最長的 subarray，而是總合最大的 subarray

一樣用 sliding window 來解題

差別在於這次要算總合，所以 left 不是直接跳到重複數字的位置

而是慢慢移過去，並把經過的數字從總合中減掉

所以可以改用 set 而不用 map，因為不用知道 index 的值

kotlin

	class Solution {
	fun maximumUniqueSubarray(nums: IntArray): Int {
	val table = mutableSetOf<Int>()
	var left = 0
	var sum = 0
	var ans = 0
	for(right in nums.indices) {
	sum += nums[right]
	while(table.contains(nums[right])) {
	sum -= nums[left]
	table.remove(nums[left])
	++left
	}
	table.add(nums[right])
	ans = Math.max(ans, sum)
	}
	return ans
	}
	}

view raw max_sum_subarray.kt hosted with ❤ by GitHub