Use HashMap to store indices⌗

See also: 3. Longest Substring Without Repeating Characters

class Solution {
public:
	int maximumUniqueSubarray(vector<int>& nums) {
		int maximum = 0;
		int left = 0, right = 0;
		unordered_map<int, int> indices;

		for (; right < nums.size(); right++) {
			int n = nums[right];
			if (indices.find(n) != indices.end() && indices[n] + 1 > left) {
				left = indices[n] + 1;
			}
			maximum = max(maximum, std::accumulate(nums.begin() + left, nums.begin() + right + 1, 0));
			indices[n] = right;
		}
		return maximum;
	}
};

It is too slow, as there is a \(O(n^2)\) time complexity(std::accmulate is the embed \(O(n)\) ).

Slide left window step by step and use HashSet to store numbers⌗

The keys we should noted:

  1. We must decrease all the numbers that behind the new left position(a while loop is used here).
class Solution {
public:
	int maximumUniqueSubarray(vector<int>& nums) {
		int maximum = 0;
		int left = 0, right = 0, sum = 0;
		unordered_set<int> hset;

		for (; right < nums.size(); right++) {
			int n = nums[right];
			while (hset.find(n) != hset.end()) {
				hset.erase(nums[left]);
				sum -= nums[left];
				left++;
			}
			sum += n;
			maximum = max(maximum, sum);
			hset.insert(n);
		}
		return maximum;
	}
};