Problem 582319 · medium · Phase 05 Advanced Algorithms & Graphs

Best Streak Product

dynamic programming · 1-D dp · max product subarray · sign tracking

A trading bot logs a daily multiplier in factors (an integer that may be negative or zero). Its performance over a contiguous block of days is the product of the multipliers in that block. Return the best performance over all non-empty contiguous blocks.

Examples

Input:  factors = [2, 3, -2, 4]
Output: 6
Explanation: the block [2, 3].

Input:  factors = [-2, 0, -1]
Output: 0

Constraints

  • 1 <= len(factors) <= 10**5
  • -9 <= factors[i] <= 9
  • No zero-free stretch is longer than 40 days, so every product fits in a normal integer range.
  • Target complexity: O(n) time.

Goals

  • Track both the largest and the smallest product ending at each index
  • Handle zeros and sign flips correctly
Starting Python…