Longest sub-array with positive product

PROBLEM STATEMENT

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

Approach 2

In this approach, we will use a simple concept of mathematics that the product of integers is positive if

All the elements are positive integers.
If there are negative integers, then the count of negative integers should be even.

If the sub-array consists of odd number of negative integers, then in order to get the positive product we have to discard one negative integer. (either the first one or the last one).

We have to take care of a corner case when an element at any index ‘ i ’ i.e ARR[ i ] = 0 because it will make the product zero.

Take variables 'START' and 'END' which indicate the starting and ending index of the sub-array. and ‘ANS' to keep the result. (all initialized to 0)
Run a loop until 'Start' < N.
Increement 'START' until ARR['Start'] = 0.and then assign 'END' = 'Start'.
Take two variables ‘FRST_NEG’ and 'LAST_NEG' (both initialized to -1) which indicate the index of the first and last negative number found in subarray and ‘CNT’ to keep count of negative numbers.
'Start' an iteration until 'END' < N and ARR['END'] != 0

if(ARR['END'] < 0), increement ‘'CNT'’ by one.

if('FRST_NEG' == -1) i.e. current element is first negative found ,then 'FRST_NEG'='END'.

Assign 'LAST_NEG'='END'.

If count ‘CNT' of negative numbers is even, then subarray from 'Start' to ‘END -1’ will give a positive product.So 'ANS'= max('ANS', 'END'-'Start').
If ‘'CNT'’ is odd, to get a positive product we have to eliminate either the first or last negative number.

'ANS' = max('ANS', 'LAST_NEG' - 'Start') [Discarding first negative integer]

'ANS'= max('ANS', 'END' - 'FRST_NEG' - 1) [Discarding last negative number]