diff options
Diffstat (limited to 'max_sum_distinct_subarr.py')
-rw-r--r-- | max_sum_distinct_subarr.py | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/max_sum_distinct_subarr.py b/max_sum_distinct_subarr.py new file mode 100644 index 0000000..28f3a84 --- /dev/null +++ b/max_sum_distinct_subarr.py @@ -0,0 +1,35 @@ +# 2461. Maximum Sum of Distinct Subarrays With Length K + +""" +you are given an integer array 'nums' and an integer 'k'. find the maximum +subarray sum of all the subarrays of 'nums' that meet the following +conditions. the length of the subarray is 'k' and all the elements of the +subarray are distinct. return the maximum subarray of all the subarrays that +meet the conditions. if no subarray meets the conditions, return 0. a +subarray is a contiguous non empty sequence of elements within an array +""" + + +class Solution(object): + def maximumSubarraySum(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + ans, curr, pos, dup = 0, 0, [-1] * 100001, -1 + for i in range(0, len(nums)): + curr += nums[i] + if i >= k: + curr -= nums[i - k] + dup = max(dup, pos[nums[i]]) + if i - dup >= k: + ans = max(ans, curr) + pos[nums[i]] = i + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumSubarraySum(nums=[1, 5, 4, 2, 9, 9, 9], k=3)) + print(obj.maximumSubarraySum(nums=[4, 4, 4], k=3)) |