New Problem Solution - "1695. Maximum Erasure Value"

haoel · haoel · commit 7cbd02ae23be · 2021-05-07T15:44:48.000+08:00
diff --git a/README.md b/README.md
@@ -103,6 +103,7 @@ LeetCode
 |1716|[Calculate Money in Leetcode Bank](https://leetcode.com/problems/calculate-money-in-leetcode-bank/) | [C++](./algorithms/cpp/calculateMoneyInLeetcodeBank/CalculateMoneyInLeetcodeBank.cpp)|Easy|
 |1711|[Count Good Meals](https://leetcode.com/problems/count-good-meals/) | [C++](./algorithms/cpp/countGoodMeals/CountGoodMeals.cpp)|Medium|
 |1710|[Maximum Units on a Truck](https://leetcode.com/problems/maximum-units-on-a-truck/) | [C++](./algorithms/cpp/maximumUnitsOnATruck/MaximumUnitsOnATruck.cpp)|Easy|
+|1695|[Maximum Erasure Value](https://leetcode.com/problems/maximum-erasure-value/) | [C++](./algorithms/cpp/maximumErasureValue/MaximumErasureValue.cpp)|Medium|
 |1694|[Reformat Phone Number](https://leetcode.com/problems/reformat-phone-number/) | [C++](./algorithms/cpp/reformatPhoneNumber/ReformatPhoneNumber.cpp)|Easy|
 |1625|[Lexicographically Smallest String After Applying Operations](https://leetcode.com/problems/lexicographically-smallest-string-after-applying-operations/) | [C++](./algorithms/cpp/lexicographicallySmallestStringAfterApplyingOperations/LexicographicallySmallestStringAfterApplyingOperations.cpp)|Medium|
 |1624|[Largest Substring Between Two Equal Characters](https://leetcode.com/problems/largest-substring-between-two-equal-characters/) | [C++](./algorithms/cpp/largestSubstringBetweenTwoEqualCharacters/LargestSubstringBetweenTwoEqualCharacters.cpp)|Easy|
diff --git a/algorithms/cpp/maximumErasureValue/MaximumErasureValue.cpp b/algorithms/cpp/maximumErasureValue/MaximumErasureValue.cpp
@@ -0,0 +1,61 @@
+// Source : https://leetcode.com/problems/maximum-erasure-value/
+// Author : Hao Chen
+// Date   : 2021-05-07
+
+/***************************************************************************************************** 
+ *
+ * You are given an array of positive integers nums and want to erase a subarray containing unique 
+ * elements. The score you get by erasing the subarray is equal to the sum of its elements.
+ * 
+ * Return the maximum score you can get by erasing exactly one subarray.
+ * 
+ * An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if 
+ * it is equal to a[l],a[l+1],...,a[r] for some (l,r).
+ * 
+ * Example 1:
+ * 
+ * Input: nums = [4,2,4,5,6]
+ * Output: 17
+ * Explanation: The optimal subarray here is [2,4,5,6].
+ * 
+ * Example 2:
+ * 
+ * Input: nums = [5,2,1,2,5,2,1,2,5]
+ * Output: 8
+ * Explanation: The optimal subarray here is [5,2,1] or [1,2,5].
+ * 
+ * Constraints:
+ * 
+ * 	1 <= nums.length <= 10^5
+ * 	1 <= nums[i] <= 10^4
+ ******************************************************************************************************/
+
+class Solution {
+public:
+    int maximumUniqueSubarray(vector<int>& nums) {
+        //unordered_map<int, int> pos;
+        const int NIL = -1;
+        int pos[10001];
+        memset(pos, NIL, sizeof(pos));
+        
+        int start=0;
+        int max_sum =0, sum = 0;
+ 
+        for(int i = 0; i < nums.size(); i++) {
+            int n = nums[i];
+            // if find duplicated number
+            if ( pos[n] != NIL) {
+                max_sum = max(max_sum, sum);
+                //remove the previous numbers until to duplicatied position 
+                for(;start <= pos[n]; start++){
+                    sum -= nums[start];
+                    pos[nums[start]] = NIL;
+                }
+            }
+            sum += n;
+            pos[n] = i;
+        }
+        max_sum = max( max_sum , sum );
+        return max_sum;
+    }
+};
