MEDIUM NC#107 Blind #6 Dynamic Programming 1D

152. Maximum Product Subarray

šŸ“– Problem

Given an integer array nums, find the subarray that has the largest product and return that product.

šŸ§  Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • ā€¢Array methods (`push`, `pop`, `shift`, `slice`)
  • ā€¢Object/Map/Set usage patterns
  • ā€¢Function parameter and return typing
  • ā€¢Array DP table updates
  • ā€¢State transition thinking
  • ā€¢Base case initialization

Logical Thinking Concepts

  • ā€¢Define invariants before coding
  • ā€¢Check edge cases first (`[]`, single element, duplicates)
  • ā€¢Estimate time/space before implementation
  • ā€¢Apply Dynamic Programming reasoning pattern

šŸ’” Approach

  • ā†’ Track both max and min at each position (negative * negative = positive)
  • ā†’ For each number: newMax = max(num, max*num, min*num)
  • ā†’ newMin = min(num, max*num, min*num)
  • ā†’ Time: O(n), Space: O(1)

šŸ§­ Prerequisites

#91 Decode Ways #139 Word Break

šŸ› ļø Hints & Pitfalls

Hints

  • ā€¢Track both max and min at each position (negative * negative = positive)
  • ā€¢For each number: newMax = max(num, max*num, min*num)
  • ā€¢newMin = min(num, max*num, min*num)

Common Pitfalls

  • ā€¢Time: O(n), Space: O(1)

šŸ§Ŗ Test Cases

Hidden tests on submit: 2

Test Case 1
Not run
Input:
maxProduct([2,3,-2,4]);
Expected:
6
Test Case 2
Not run
Input:
maxProduct([-2,0,-1]);
Expected:
0
Test Case 3
Not run
Input:
maxProduct([-2,3,-4]);
Expected:
24

šŸ“ Code Editor

šŸ“š Reference Solution

ā–¼

šŸ”— Related Problems

#91 Decode Ways #139 Word Break #198 House Robber #213 House Robber II #300 Longest Increasing Subsequence
āŒ˜K Search āŒ˜ā†© Run āŒ˜S Submit