LeetCode #152: Maximum Product Subarray — Track the Minimum Too

Problem #152 of the Brute To Best series: Maximum Product Subarray. Find the contiguous subarray with the largest product. The sum version needs one running value; products need two, because a negative number turns the smallest running product into the largest. In this video: Why this is not just Kadane's algorithm with multiplication The brute force: every start and end, multiplying as you go, O(n squared) The case that breaks a single running maximum: a negative followed by a negative Tracking two values: the largest and smallest product ending at each index Why a negative number swaps the roles of those two The three candidates at each step: the number alone, number times max, number times min Why the number alone is needed and handles starting fresh Computing the new max before overwriting the old one How a zero resets both running values Why the answer must be updated every iteration, not only at the end Handling an all-negative array and a single element Dry run with [2,3,-2,4] reaching 6 Time O(n), space O(1) LeetCode 152 — Maximum Product Subarray: https://leetcode.com/problems/maximum... Maximum Subarray is the additive version, where one running value is enough. Earlier in the series: problems #1 to #151, in order. Subscribe to Brute To Best — every problem, from the brute force to the best solution. #leetcode #maximumproductsubarray #arrays #dynamicprogramming #kadane #greedy #onepass #dsa #coding #codinginterview #problemsolving #datastructuresandalgorithms #leetcodesolutions #brutetobest #mediumproblems