BudiBadu Logo

Maximum Product Subarray

Array Hard 0 views
Like28

You are given an integer array nums Your task is to find the contiguous subarray containing at least one number that has the largest product and return that product The subarray must be a sequence of consecutive elements within the array not necessarily unique and its length can vary from 1 to the entire array Unlike sum-related problems this task requires considering both positive and negative values because multiplying by a negative number can invert the outcome For example two negative numbers can create a larger positive product while zeros can interrupt the sequence and reset progress Handling such dynamic changes makes this problem an interesting challenge in reasoning about subarray boundaries and maintaining multiple states as you traverse the array This problem illustrates the importance of tracking both the maximum and minimum products up to each point since a large negative product might turn into a large positive product later It s widely used to understand optimization under multiplicative relationships If the array has only one element that element itself is the maximum product Zeros may appear anywhere and should be treated as separators between subarrays Because this is a counting optimization-style challenge dynamic programming is usually the safest approach define what each index or state means initialize valid base states and make transitions explicit If the problem uses modulo arithmetic apply modulo at every accumulation step so large intermediate totals never corrupt the final answer At hard difficulty

Examples

Example 1
Input
nums = [2,3,-2,4]
Output
6
Explanation

Example with input: nums = [2,3,-2,4]

Example 2
Input
nums = [-2,3,-4]
Output
24
Explanation

Example with input: nums = [-2,3,-4]

Example 3
Input
nums = [-2,0,-1]
Output
0
Explanation

Example with input: nums = [-2,0,-1]

Algorithm Flow

Recommendation Algorithm Flow for Maximum Product Subarray - Budibadu
Recommendation Algorithm Flow for Maximum Product Subarray - Budibadu

Best Answers

java
class Solution {
    public int max_product(int[] nums) {
        if (nums.length == 0) return 0;
        int res = nums[0], maxP = nums[0], minP = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            if (x < 0) {
                int tmp = maxP; maxP = minP; minP = tmp;
            }
            maxP = Math.max(x, maxP * x);
            minP = Math.min(x, minP * x);
            res = Math.max(res, maxP);
        }
        return res;
    }
}