aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-21 19:10:38 -0600
committerJack Sangdahl <[email protected]>2025-07-21 19:10:38 -0600
commit28d1b606f96d9a79657cf213b15b319fdc534945 (patch)
treeaf3febf36529e760d0498017b5e498d51e3db8a3
parent47bee99eb4f23e27ad973d2acebe911bf21d09c4 (diff)
downloadleetcode-28d1b606f96d9a79657cf213b15b319fdc534945.tar.gz
leetcode-28d1b606f96d9a79657cf213b15b319fdc534945.zip
1695. maximum erasure value
-rw-r--r--maximum_erasure_value.c40
-rw-r--r--maximum_erasure_value.py37
2 files changed, 77 insertions, 0 deletions
diff --git a/maximum_erasure_value.c b/maximum_erasure_value.c
new file mode 100644
index 0000000..3788faa
--- /dev/null
+++ b/maximum_erasure_value.c
@@ -0,0 +1,40 @@
+// 1695. Maximum Erasure Value
+#include "leetcode.h"
+
+/*
+ * you are given an array of posiive 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)'
+ */
+
+static u_char vis[1250];
+
+bool test(int a) { return vis[a >> 3] & (1 << (a & 7)) ? true : false; }
+
+void set(int a) { vis[a >> 3] |= 1 << (a & 7); }
+
+void reset(int a) { vis[a >> 3] &= ~(1 << (a & 7)); }
+
+int maximumUniqueSubarray(int *nums, int numsSize) {
+ int ans = 0, sum = 0;
+ memset(vis, 0, sizeof(vis));
+ for (int i = 0, j = 0; i < numsSize; i++) {
+ while (test(nums[i] - 1)) {
+ sum -= nums[j];
+ reset(nums[j++] - 1);
+ }
+ sum += nums[i];
+ set(nums[i] - 1);
+ ans = fmax(ans, sum);
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {4, 2, 4, 5, 6}, n2[] = {5, 2, 1, 2, 5, 2, 1, 2, 5};
+ printf("%d\n", maximumUniqueSubarray(n1, ARRAY_SIZE(n1))); // expect: 17
+ printf("%d\n", maximumUniqueSubarray(n2, ARRAY_SIZE(n2))); // expect: 8
+}
diff --git a/maximum_erasure_value.py b/maximum_erasure_value.py
new file mode 100644
index 0000000..227e3c9
--- /dev/null
+++ b/maximum_erasure_value.py
@@ -0,0 +1,37 @@
+# 1695. Maximum Erasure Value
+
+"""
+you are given an array of posiive 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)'
+"""
+
+
+class Solution(object):
+ def maximumUniqueSubarray(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ beg, end, ans = 0, 0, 0
+ s, n, m = set(), len(nums), 0
+ while end < n:
+ if nums[end] not in s:
+ m += nums[end]
+ s.add(nums[end])
+ end += 1
+ ans = max(ans, m)
+ else:
+ m -= nums[beg]
+ s.remove(nums[beg])
+ beg += 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maximumUniqueSubarray(nums=[4, 2, 4, 5, 6]))
+ print(obj.maximumUniqueSubarray(nums=[5, 2, 1, 2, 5, 2, 1, 2, 5]))