RUST GYM Leetcode 689 Maximum Sum of 3 Non-Overlapping Subarrays Rust Solution

689. Maximum Sum of 3 Non-Overlapping Subarrays

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

Example:

Input: [1,2,1,2,6,7,5,1], 2
Output: [0, 3, 5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

Note:

nums.length will be between 1 and 20000.
nums[i] will be between 1 and 65535.
k will be between 1 and floor(nums.length / 3).

Rust Solution

struct Solution;

impl Solution {
    fn max_sum_of_three_subarrays(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let sums: Vec<i32> = nums.windows(k).map(|w| w.iter().sum()).collect();
        let n = sums.len();
        let mut left = vec![];
        let mut left_max = 0;
        let mut left_index = 0;
        for i in 0..n {
            if sums[i] > left_max {
                left_max = sums[i];
                left_index = i;
            }
            left.push((left_max, left_index));
        }

        let mut right = vec![];
        let mut right_max = 0;
        let mut right_index = n;
        for i in (0..n).rev() {
            if sums[i] >= right_max {
                right_max = sums[i];
                right_index = i;
            }
            right.push((right_max, right_index));
        }
        right.reverse();
        let mut mid_max = 0;
        let mut res = vec![0, 0, 0];
        for i in k..n - k {
            let sum_3 = sums[i] + left[i - k].0 + right[i + k].0;
            if sum_3 > mid_max {
                mid_max = sum_3;
                res = vec![left[i - k].1, i, right[i + k].1];
            }
        }
        res.into_iter().map(|x| x as i32).collect()
    }
}

#[test]
fn test() {
    let nums = vec![1, 2, 1, 2, 6, 7, 5, 1];
    let k = 2;
    let res = vec![0, 3, 5];
    assert_eq!(Solution::max_sum_of_three_subarrays(nums, k), res);
}

Having problems with this solution? Click here to submit an issue on github.