leetcode

commit f42abd7454ae390e446d6d43c99113706982d0e9
parent 5dff7aff23df1e8b2a2a817799ee7c9c27b789f1
Author: Louis Burda <quent.burda@gmail.com>
Date:   Wed, 20 Nov 2024 22:18:49 +0100

Add problem 2461

Diffstat:
M
Cargo.toml
 | 
4
++++
A
src/bin/2461-maximum-sum-of-distinct-subarrays-with-length-k.rs
 | 
86
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 90 insertions(+), 0 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
@@ -24,6 +24,10 @@ name = "2463"
 path = "src/bin/2463-minimum-total-distance-traveled.rs"
 
 [[bin]]
+name = "2461"
+path = "src/bin/2461-maximum-sum-of-distinct-subarrays-with-length-k.rs"
+
+[[bin]]
 name = "1671"
 path = "src/bin/1671-minimum-number-of-removals-to-make-mountain-array.rs"
 
diff --git a/src/bin/2461-maximum-sum-of-distinct-subarrays-with-length-k.rs b/src/bin/2461-maximum-sum-of-distinct-subarrays-with-length-k.rs
@@ -0,0 +1,86 @@
+/// 2461. Maximum Sum of Distinct Subarrays With Length K (Medium)
+///
+/// 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 sum 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.
+///
+/// *Example 1:*
+///
+///   *Input:* nums = [1,5,4,2,9,9,9], k = 3
+///   *Output:* 15
+///   *Explanation:* The subarrays of nums with length 3 are:
+///   - [1,5,4] which meets the requirements and has a sum of 10.
+///   - [5,4,2] which meets the requirements and has a sum of 11.
+///   - [4,2,9] which meets the requirements and has a sum of 15.
+///   - [2,9,9] which does not meet the requirements because the element 9 is
+///     repeated.
+///   - [9,9,9] which does not meet the requirements because the element 9 is
+///     repeated.
+///   We return 15 because it is the maximum subarray sum of all the subarrays
+///   that meet the conditions
+///
+/// *Example 2:*
+///
+///   *Input:* nums = [4,4,4], k = 3
+///   *Output:* 0
+///   *Explanation:* The subarrays of nums with length 3 are:
+///   - [4,4,4] which does not meet the requirements because the element 4 is
+///     repeated.
+///   We return 0 because no subarrays meet the conditions.
+///
+/// *Constraints:*
+///
+///   * 1 <= k <= nums.length <= 105
+///   * 1 <= nums[i] <= 105
+///
+
+use leetcode::*;
+use std::cmp;
+
+struct Solution {}
+
+impl Solution {
+    pub fn maximum_subarray_sum(nums: Vec<i32>, k: i32) -> i64 {
+        let n = nums.len();
+        let mut lut = [-1i32; 100001];
+        let mut violation = -1i32;
+        let mut best = 0i64;
+        let mut sum = 0i64;
+        for i in 0..n {
+            let window_start = ((i as i32) - k + 1).max(0);
+            violation = violation.max(lut[nums[i] as usize]);
+            lut[nums[i] as usize] = i as i32;
+            sum += nums[i] as i64;
+            if i as i32 >= k - 1 {
+                if violation < window_start {
+                    best = cmp::max(best, sum);
+                }
+                sum -= nums[window_start as usize] as i64;
+            }
+        }
+        best
+    }
+}
+
+pub fn main() {
+    println!("{}", Solution::maximum_subarray_sum(arg_into(1), arg_into(2)));
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::Solution;
+
+    #[test]
+    fn test() {
+        assert_eq!(Solution::maximum_subarray_sum(vec![1,5,4,2,9,9,9], 3), 15);
+        assert_eq!(Solution::maximum_subarray_sum(vec![4,4,4], 3), 0);
+    }
+}