NUHMAN.com

Introduction

LeetCode 152 asks us to find the contiguous subarray within a given integer array nums that has the largest product. The subarray can consist of positive or negative integers, and our goal is to find the maximum product that can be obtained.

This problem can be tricky due to the presence of negative numbers, which can flip the product signs. Therefore, it's not just about keeping track of the maximum product but also the minimum product, as a large negative product could turn positive when multiplied by another negative number.

Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest product and return its product.

Function Signature:

go

func maxProduct(nums []int) int

Approach

Key Idea:

To solve this problem efficiently, we can use Dynamic Programming (DP). The idea is to track two values as we iterate through the array:

• maxProduct: The maximum product up to the current index.
• minProduct: The minimum product up to the current index.

Why do we need both maxProduct and minProduct?

• maxProduct: This helps us track the maximum product found so far, considering that multiplying a negative number by a negative number may result in a larger positive product.
• minProduct: Similarly, we also need to track the smallest product in case it turns into the largest when multiplied by a negative number.

At each step, we update these two values:

1. Multiply the current number with both the maxProduct and minProduct (because multiplying negative numbers might flip signs).
2. The maximum product at each step will be the maximum of the current number itself, the number multiplied by maxProduct, and the number multiplied by minProduct.
3. Similarly, the minimum product at each step will be the minimum of these three values.

The time complexity of this approach is O(n), where n is the length of the array, and we use O(1) space.

Go Implementation

go

package main

import "fmt"

func maxProduct(nums []int) int {
	// Initialize the maximum and minimum products
	maxProduct, minProduct := nums[0], nums[0]
	// Initialize the result to track the global maximum product
	result := nums[0]

	// Traverse through the array starting from the second element
	for i := 1; i < len(nums); i++ {
		// If the current number is negative, swap maxProduct and minProduct
		if nums[i] < 0 {
			maxProduct, minProduct = minProduct, maxProduct
		}

		// Update the maxProduct and minProduct
		maxProduct = max(nums[i], maxProduct*nums[i])
		minProduct = min(nums[i], minProduct*nums[i])

		// Update the result with the maximum product so far
		result = max(result, maxProduct)
	}

	return result
}

// Helper function to get the maximum of two numbers
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// Helper function to get the minimum of two numbers
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	// Example usage
	nums := []int{2, 3, -2, 4}
	result := maxProduct(nums)
	fmt.Println("Maximum Product Subarray:", result) // Output: 6
}

Explanation of the Code:

1. Initialization:

• We start by initializing maxProduct, minProduct, and result to the first element of the array. This ensures we are starting with a valid value for the first iteration.

1. Iterating Through the Array:

• We then loop through the array starting from the second element (i := 1).
• If the current number is negative, we swap maxProduct and minProduct because multiplying by a negative number flips the signs.

1. Updating the Products:

• We update maxProduct to be the maximum of the current number itself or the current number multiplied by the previous maxProduct.
• Similarly, we update minProduct to track the minimum product in the same way.

1. Result:

• After updating the maxProduct and minProduct at each step, we compare result with maxProduct and update result with the larger value.

1. Helper Functions:

• max(a, b) returns the larger of a and b.
• min(a, b) returns the smaller of a and b.

Time and Space Complexity

OperationComplexityTimeO(n)SpaceO(1)

• Time Complexity:
• We only need one pass over the array, so the time complexity is O(n), where n is the length of the array.
• Space Complexity:
• We are only using a few variables to store the results and intermediate values, so the space complexity is O(1).

Example

Input:

go

nums := []int{2, 3, -2, 4}

Output:

6

Explanation:

1. First iteration (2):

• maxProduct = 2, minProduct = 2, result = 2

1. Second iteration (3):

• maxProduct = 6 (3 * 2), minProduct = 3, result = 6

1. Third iteration (-2):

• After swapping maxProduct and minProduct because the number is negative:
• maxProduct = 3, minProduct = -12 (-2 * 6).
• result = 6

1. Fourth iteration (4):

• maxProduct = 12 (4 * 3), minProduct = -48, result = 12

Final result: 6.

Why This Approach Works

• Efficient: This solution is very efficient, operating in linear time with constant space. We only need to keep track of the current maxProduct and minProduct to update the result, and we process each element of the array once.
• Handles Negative Numbers: The key insight is recognizing that a negative number can flip the signs of both the maximum and minimum products, which is why we track both the maximum and minimum products simultaneously.

Conclusion

This problem showcases the power of dynamic programming and the importance of maintaining both maximum and minimum products in cases where negative numbers might reverse the sign of the product. By updating both values in each iteration, we efficiently solve the problem in O(n) time and O(1) space.