impl Solution {
    pub fn max_sum_of_three_subarrays(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize; // Convert k to usize for indexing
        let n = nums.len();
        if n < 3 * k {
            panic!("Not enough elements for three subarrays");
        }

        // Step 1: Compute sums of all subarrays of length k
        let window_sums = Self::compute_window_sums(&nums, k);

        // Step 2: Compute the best indices for the rightmost subarray
        let max_right_indices = Self::compute_max_right_indices(&window_sums);

        // Step 3: Find the best split for two subarrays
        let best_two_subarrays = Self::compute_best_two_subarrays(&window_sums, k);

        // Step 4: Find the optimal three subarrays
        let result = Self::find_best_three_subarrays(&window_sums, &best_two_subarrays, &max_right_indices, k);

        result
    }

    // Compute the sum of all sliding windows of size k
    fn compute_window_sums(nums: &[i32], k: usize) -> Vec<i32> {
        let n = nums.len();
        let mut window_sums = vec![0; n - k + 1];
        let mut sum = 0;

        // Use a sliding window to calculate sums
        for i in 0..n {
            sum += nums[i];
            if i >= k {
                sum -= nums[i - k]; // Subtract the element going out of the window
            }
            if i >= k - 1 {
                window_sums[i - k + 1] = sum; // Store the sum for the current window
            }
        }
        window_sums
    }

    // Find the indices of the maximum subarray sum for each position, scanning from right to left
    fn compute_max_right_indices(window_sums: &[i32]) -> Vec<usize> {
        let mut max_right_indices = vec![0; window_sums.len()];
        max_right_indices[window_sums.len() - 1] = window_sums.len() - 1;

        // Iterate from right to left to track the best starting indices
        for i in (0..window_sums.len() - 1).rev() {
            if window_sums[i] >= window_sums[max_right_indices[i + 1]] {
                max_right_indices[i] = i; // Update if current sum is greater or equal
            } else {
                max_right_indices[i] = max_right_indices[i + 1]; // Carry forward the best index
            }
        }
        max_right_indices
    }

    // Find the best split for two subarrays (left and middle), using dynamic programming
    fn compute_best_two_subarrays(window_sums: &Vec<i32>, k: usize) -> Vec<(usize, usize, i32)> {
        let mut best_left_sum = 0;
        let mut best_left_index = 0;
        let mut best_two_subarrays = vec![(0, 0, 0); window_sums.len() + k + 1];

        // Iterate to find the best combination of left and middle subarrays
        for i in k..window_sums.len() {
            if window_sums[i - k] > best_left_sum {
                best_left_sum = window_sums[i - k]; // Update the best sum for the left subarray
                best_left_index = i - k; // Track the index of the left subarray
            }
            let current_sum = best_left_sum + window_sums[i]; // Calculate total sum for left + middle
            best_two_subarrays[i + k] = best_two_subarrays[i + k - 1]; // Carry forward previous best
            if current_sum > best_two_subarrays[i + k - 1].2 {
                best_two_subarrays[i + k] = (best_left_index, i, current_sum); // Update if better split found
            }
        }
        best_two_subarrays
    }

    // Find the best split for three subarrays (left, middle, and right)
    fn find_best_three_subarrays(
        window_sums: &[i32],
        best_two_subarrays: &[(usize, usize, i32)],
        max_right_indices: &[usize],
        k: usize,
    ) -> Vec<i32> {
        let mut result = (0, k, 2 * k);
        let mut max_sum = window_sums[0] + window_sums[k] + window_sums[2 * k];

        // Iterate to find the optimal combination of left, middle, and right subarrays
        for i in 2 * k..window_sums.len() {
            let third_index = max_right_indices[i]; // Best starting index for the right subarray
            let current_sum = best_two_subarrays[i].2 + window_sums[third_index]; // Total sum of three subarrays
            if current_sum > max_sum {
                max_sum = current_sum; // Update max sum if a better split is found
                result = (
                    best_two_subarrays[i].0,
                    best_two_subarrays[i].1,
                    third_index,
                );
            }
        }
        vec![result.0 as i32, result.1 as i32, result.2 as i32]
    }
}