Maximum Erasure Value
给一个数组, 求里面和最大的不同元素子数组的和是多少
直接算超时
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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就过了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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; } } |