Longest sub-array with positive product

Posted: 28 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given an array ‘ARR’ of ‘N’ integers, you need to find the maximum length of the sub-array such that the product of elements of the sub-array is positive.

For Example:
Let us say we have array 'ARR' =[-1,3,5,-2,4,-9]. The longest sub-array with the positive product is [3,5,-2,4,-9]. 
Input Format
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains ‘N’ which is the number of elements in the array.

The second line of each test case contains ‘N’ space-separated integers that make up ‘ARR’.
Output Format
For each test case, print a single line containing a single integer denoting the length of the longest sub-array with a positive product.

The output of each test case will be printed in a separate line.
Note
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints
1 <= T <= 50
1 <= N <= 10 ^ 5
-10 ^ 8 <= ARR[i] <= 10 ^ 8

Time Limit: 1 sec.
Approach 1

A naive approach is to iterate through all elements and examine the product of all the possible sub-arrays. But we have to only check whether the product is positive or not, so instead of multiplying numbers, we will multiply only the signs of numbers.

 

Algorithm:

  • Take a variable ‘PR’ to keep the product and ‘ANS’ (initialized to 0) to store the result.
  • Run three loops
    • ‘i’ : 0 to ‘N - 1’
    • ‘j’ : ‘i’  to ‘N - 1’
    • ‘k’ : ‘i’ to ‘j’
  • ‘i’ indicates the starting index of the current sub-array, and ‘j’ indicates the sub-array’s ending index.
  • Run loop of ‘k’ from ‘i’ to ‘j’
    • If (ARR [k] > 0 ) , ‘PR' = ‘PR’ * 1;
    • If (ARR [k] < 0 ) , 'PR' = 'PR' * -1;
    • If (ARR [k] > 0 ) , ‘PR’ = ‘PR’ * 0;
  • If ‘PR’ > 0, update ‘ANS’ as ‘ANS’ =max(ANS, j - i + 1).
  • Return ‘ANS’.
Try Problem