diff options
author | Jack Sangdahl <[email protected]> | 2025-07-21 19:10:38 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-07-21 19:10:38 -0600 |
commit | 28d1b606f96d9a79657cf213b15b319fdc534945 (patch) | |
tree | af3febf36529e760d0498017b5e498d51e3db8a3 | |
parent | 47bee99eb4f23e27ad973d2acebe911bf21d09c4 (diff) | |
download | leetcode-28d1b606f96d9a79657cf213b15b319fdc534945.tar.gz leetcode-28d1b606f96d9a79657cf213b15b319fdc534945.zip |
1695. maximum erasure value
-rw-r--r-- | maximum_erasure_value.c | 40 | ||||
-rw-r--r-- | maximum_erasure_value.py | 37 |
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])) |