Maximum Erasure Value
给一个数组, 求里面和最大的不同元素子数组的和是多少
直接算超时
class Solution {
public int maximumUniqueSubarray(int[] nums) {
Set<Integer> set = new HashSet<>();
int i = 0;
int j = 0;
int res = 0;
int tmp = 0;
while(j < nums.length) {
if(!set.contains(nums[j])){
set.add(nums[j]);
tmp += nums[j];
j++;
}else{
res = Math.max(res, tmp);
//reset
set.clear();
tmp = 0;
i++;
j = i;
}
}
res = Math.max(res, tmp);
return res;
}
}
PreSum就过了
class Solution {
public int maximumUniqueSubarray(int[] nums) {
Set<Integer> set = new HashSet<>();
int[] pre = new int[nums.length + 1];
for(int i = 1; i < nums.length + 1; i++) {
pre[i] = pre[i - 1] + nums[i - 1];
}
Map<Integer, Integer> map = new HashMap<>();
int i = 0;
int j = 0;
int res = 0;
while(j < nums.length) {
if(map.containsKey(nums[j])){
i = Math.max(i, map.get(nums[j]) + 1);
}
res = Math.max(res, pre[j + 1] - pre[i]);
map.put(nums[j], j);
j++;
}
return res;
}
}