C++ | O(n) | Single-pass | Map + Prefix Sum
The goal of the algorithm to solve this problem was to maximize sum(i,j) such that all elements from i to j are unique (where sum(i,j) for array A is A[i] + A[i
The goal of the algorithm to solve this problem was to **maximize** `sum(i,j)` such that all elements from **i** to **j** are **unique** (where `sum(i,j)` for array `A` is `A[i] + A[i+1] + .. A[j-1] + A[j]`).\nWe can think it in terms of **j**, for every **j**, we want to find the **left-most** point in the array such that elements are **unique** between them. The answer would be the **maximum** of all computed **j** values.\n\nWe can create a prefix array to compute `sum(i,j)`.\n\nAlgorithm:\n\n1. Set `left` = -1, `n` = `nums`.size(), create prefix array\n2. For all `j` from `[0...n-1]`\n\t1. If `nums[j]` is **already encountered** && **previous index** of `nums[j]` is greater than `left`\n\t2. Then set `left` = **previous index** of `nums[j]`\n\t3. end if\n\t4. Set index of `nums[j]` to `j`\n\t5. store answer for `j` = `sum(left+1, j)` using **prefix array**\n3. return **maximum** of answer for each `j`.\n\n*Note: We can club creating prefix array in single loop.*\n\nCode:\n```\nint maximumUniqueSubarray(vector<int>& nums) {\n\tunordered_map<int,int> idx;\n\tint n = nums.size();\n\tint ans = 0;\n\tvector<int> prefix(n+1, 0);\n\n\tint left = -1;\n\tfor(int i = 0; i<n; i++){\n\t\t//build prefix on-the-fly\n\t\tprefix[i+1] = prefix[i] + nums[i];\n\n\t\t// pick left index untill elements are unique\n\t\tif(idx.count(nums[i]) > 0 && left < idx[nums[i]]) left = idx[nums[i]];\n\n\t\t//update map with latest index of element\n\t\tidx[nums[i]] = i;\n\t\t\n\t\t//use prefix array to calculate the sum in O(1)\n\t\tans = max(ans, prefix[i+1] - prefix[left+1]);\n\t}\n\n\treturn ans;\n\n}\n```\n\nComplexity analysis:\n\n**Time Complexity (Average Case)**\n| Operation | Upperbound |\n|---------------|------------------|\n| Building Prefix| O(n) |\n|Accessing Map| O(1)|\n|Using prefix| O(1)|\n\nTime complexitity is `O(n * (k1+k2))` = **`O(n)`**, where `k1` and `k2` are constants.\n\n**Space Complexity (Avearage Case)**\n| Operation | Upperbound |\n|---------------|------------------|\n| Prefix | O(n) |\n|Map| O(n)|\n\nSpace complexitity is `O(n + n)` = **`O(n)`**\n\n![image](https://assets.leetcode.com/users/images/56417c24-0be4-447f-ad34-f5f54396b7e0_1654862411.517765.png)\n\n*`Shikhar03Stark`*\n\n\n
['Two Pointers', 'C', 'Prefix Sum']