What is the brute force approach and complexity for Maximum Length of Subarray With Positive Product?

For each start, walk right counting negatives; stop at a zero with time complexity O(N^2) and space complexity O(1).

How do you identify the pattern for Maximum Length of Subarray With Positive Product?

Look for key signals in the prompt: "contiguous" indicates Still a range, so we walk left to right and look back once at the state of the block ending before.; "positive product" indicates Only the sign of the product matters: an even number of negatives and no zero.; "longest length" indicates Track the best length for each sign, not a single length..

Maximum Length of Subarray With Positive Product

Medium·LeetCode #1567 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given an integer array nums. Look at every contiguous block of numbers next to each other. The product of a block is all its numbers multiplied together.

Return the length of the longest block whose product is positive. A product of 0 does not count as positive.

Input

An integer array nums of length n.

Output

A single integer: the length of the longest contiguous block with a positive product. Return 0 if there is none.

Example 1

Input: nums = [1, -2, -3, 4]

Output: 4

The whole array has two negative numbers, so the product is 1 · (-2) · (-3) · 4 = 24. That is positive, so the length is 4.

Example 2

Input: nums = [0, 1, -2, -3, -4]

Output: 3

The 0 cuts the array into parts. The block [1, -2, -3] has two negatives, so its product 6 is positive. Its length is 3.

Example 3

Input: nums = [-1, -2, -3, 0, 1]

Output: 2

The block [-1, -2] has two negatives, so its product is 2. Any longer block would have to include the 0 or an odd number of negatives.

Constraints

• 1 ≤ nums.length ≤ 10^5
• −10^9 ≤ nums[i] ≤ 10^9

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“contiguous”

→ Still a range, so we walk left to right and look back once at the state of the block ending before.

“positive product”

→ Only the sign of the product matters: an even number of negatives and no zero.

“longest length”

→ Track the best length for each sign, not a single length.

Approach Complexity Ladder

Brute Force — count negatives from each startO(N^2)O(1)

For each start, walk right counting negatives; stop at a zero

Optimal — two running lengths: positive and negativeO(N)O(1)

Track the longest block ending here with a positive and with a negative product; a negative number swaps them

Brute Force Intuition

A block's sign depends only on how many negative numbers it has and whether it has a zero. So for each start, walk right, count the negatives, and stop when you reach a zero. An even count means the product is positive, so that block's length is a candidate.

Recognition rule for this sub-pattern:

A negative flips max and min — track both.

Remember this · DP — Kadane / Subarray

Trigger

Maximum (or minimum) sum/product of a contiguous subarray, stock buy/sell, circular arrays.

Think

Is the best subarray ending at i either "i alone" or "best ending at i−1, plus i"?

Key question

Should I extend or restart?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Kadane / Subarray translate into production architectures and low-level memory mechanics.

LLD Architecture