Maximum product subarray

Array Dynamic Programming

36.0% acceptance

Jan 12, 2026

20290

825

Given an integer array nums, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer. Note that the product of an array with a single element is the value of that element.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_product(nums: Vec<i32>) -> i32 {
    let mut max_so_far = nums[0];
    let mut max_ending_here = nums[0];
    let mut min_ending_here = nums[0];
    
    for i in 1..nums.len() {
      let temp_max = max_ending_here;
      max_ending_here = nums[i]
        .max(nums[i] * max_ending_here)
        .max(nums[i] * min_ending_here);
      min_ending_here = nums[i]
        .min(nums[i] * temp_max)
        .min(nums[i] * min_ending_here);
      max_so_far = max_so_far.max(max_ending_here);
    }
    
    max_so_far
  }
}