Rust - Dynamic Programming(Prefix Sums), with Monotonic Stack
Problem List of Dedicated "Prefix Sums" - github\n\nProblem List of "Special Array" techinique - github\n\nProblem List of "Monotonic Stack" - github\n\nProblem
[Problem List of Dedicated "Prefix Sums" - github](https://github.com/An7One/leetcode-problems-by-tag-an7one/blob/main/txt/by_algorithm/dynamic_programming/prefix_vs_suffix_sums.txt)\n\n[Problem List of "Special Array" techinique - github](https://github.com/An7One/leetcode-problems-by-tag-an7one/tree/main/txt/by_algorithm/dynamic_programming/by_technique/with_help_of/special_array)\n\n[Problem List of "Monotonic Stack" - github](https://github.com/An7One/leetcode-problems-by-tag-an7one/blob/main/txt/by_data_structure/stack/stack_monotonic.txt)\n\n[Problem List of "Subarray" - github](https://github.com/An7One/leetcode-problems-by-tag-an7one/blob/main/txt/by_data_structure/array/by_data_structure/subarray.txt)\n\n```\n/// https://leetcode.com/problems/maximum-subarray-min-product/\n/// \n/// Time Complexity:    O(`len_n`)\n/// Space Complexity:   O(`len_n`)\n/// \n/// Reference:\n/// https://leetcode.com/problems/maximum-subarray-min-product/discuss/1198718/JavaPython-Stack-keeps-index-of-elements-less-than-numsi-O(N)\nuse std::collections::VecDeque;\n\nimpl Solution {\n    pub fn max_sum_min_product(nums: Vec<i32>) -> i32 {\n        const MOD: u64 = 1e9 as u64 + 7;\n        let len_n = nums.len();\n        \n        let mut left_bound: Vec<usize> = vec![0; len_n];\n        let mut right_bound: Vec<usize> = vec![0; len_n];\n        \n        let mut stack: VecDeque<usize> = VecDeque::new();\n        for i in 0..len_n{\n            while let Some(&top) = stack.back(){\n                if nums[top] >= nums[i] {\n                    stack.pop_back();\n                }else{\n                    break;\n                }\n            }\n            \n            if let Some(&top) = stack.back(){\n                left_bound[i] = top + 1;\n            }else{\n                left_bound[i] = 0;\n            }\n            \n            stack.push_back(i);\n        }\n        \n        stack.clear();\n        \n        for i in (0..len_n).rev(){\n            while let Some(&top) = stack.back(){\n                if nums[top] >= nums[i]{\n                    stack.pop_back();\n                }else{\n                    break;\n                }\n            }\n            \n            if let Some(&top) = stack.back(){\n                right_bound[i] = top - 1;\n            }else{\n                right_bound[i] = len_n - 1;\n            }\n            \n            stack.push_back(i);\n        }\n        \n        let mut prefix_sums: Vec<u64> = vec![0; len_n + 1];\n        for i in 0..len_n{\n            prefix_sums[i + 1] = prefix_sums[i] + nums[i] as u64; \n        }\n        \n        let mut max_product: u64 = 0;\n        for i in 0..len_n{\n            max_product = std::cmp::max(max_product, Self::get_sum(left_bound[i], right_bound[i], &prefix_sums) * (nums[i] as u64));\n        }\n        \n        (max_product % MOD) as i32\n    }\n    \n    fn get_sum(lo: usize, hi: usize, prefix_sums: &Vec<u64>) -> u64{\n        return prefix_sums[hi + 1] - prefix_sums[lo];\n    }\n}\n```
['Dynamic Programming', 'Monotonic Stack', 'Rust']