leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

2461-maximum-sum-of-distinct-subarrays-with-length-k.rs (2760B)

      1/// 2461. Maximum Sum of Distinct Subarrays With Length K (Medium)
      2///
      3/// You are given an integer array nums and an integer k. Find the maximum
      4/// subarray sum of all the subarrays of nums that meet the following
      5/// conditions:
      6///
      7///   * The length of the subarray is k, and
      8///   * All the elements of the subarray are *distinct*.
      9///
     10/// Return the maximum subarray sum of all the subarrays that meet the
     11/// conditions. If no subarray meets the conditions, return 0.
     12///
     13/// A *subarray* is a contiguous non-empty sequence of elements within an array.
     14///
     15/// *Example 1:*
     16///
     17///   *Input:* nums = [1,5,4,2,9,9,9], k = 3
     18///   *Output:* 15
     19///   *Explanation:* The subarrays of nums with length 3 are:
     20///   - [1,5,4] which meets the requirements and has a sum of 10.
     21///   - [5,4,2] which meets the requirements and has a sum of 11.
     22///   - [4,2,9] which meets the requirements and has a sum of 15.
     23///   - [2,9,9] which does not meet the requirements because the element 9 is
     24///     repeated.
     25///   - [9,9,9] which does not meet the requirements because the element 9 is
     26///     repeated.
     27///   We return 15 because it is the maximum subarray sum of all the subarrays
     28///   that meet the conditions
     29///
     30/// *Example 2:*
     31///
     32///   *Input:* nums = [4,4,4], k = 3
     33///   *Output:* 0
     34///   *Explanation:* The subarrays of nums with length 3 are:
     35///   - [4,4,4] which does not meet the requirements because the element 4 is
     36///     repeated.
     37///   We return 0 because no subarrays meet the conditions.
     38///
     39/// *Constraints:*
     40///
     41///   * 1 <= k <= nums.length <= 105
     42///   * 1 <= nums[i] <= 105
     43///
     44use leetcode::*;
     45use std::cmp;
     46
     47struct Solution {}
     48
     49impl Solution {
     50    pub fn maximum_subarray_sum(nums: Vec<i32>, k: i32) -> i64 {
     51        let n = nums.len();
     52        let mut lut = [-1i32; 100001];
     53        let mut violation = -1i32;
     54        let mut best = 0i64;
     55        let mut sum = 0i64;
     56        for i in 0..n {
     57            let window_start = ((i as i32) - k + 1).max(0);
     58            violation = violation.max(lut[nums[i] as usize]);
     59            lut[nums[i] as usize] = i as i32;
     60            sum += nums[i] as i64;
     61            if i as i32 >= k - 1 {
     62                if violation < window_start {
     63                    best = cmp::max(best, sum);
     64                }
     65                sum -= nums[window_start as usize] as i64;
     66            }
     67        }
     68        best
     69    }
     70}
     71
     72pub fn main() {
     73    println!(
     74        "{}",
     75        Solution::maximum_subarray_sum(arg_into(1), arg_into(2))
     76    );
     77}
     78
     79#[cfg(test)]
     80mod tests {
     81    use crate::Solution;
     82    use leetcode::vi;
     83
     84    #[test]
     85    fn test() {
     86        assert_eq!(Solution::maximum_subarray_sum(vi("[1,5,4,2,9,9,9]"), 3), 15);
     87        assert_eq!(Solution::maximum_subarray_sum(vi("[4,4,4]"), 3), 0);
     88    }
     89}