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;
    }
}