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].
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’.
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.
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 50
1 <= N <= 10 ^ 5
-10 ^ 8 <= ARR[i] <= 10 ^ 8
Time Limit: 1 sec.
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:
In this approach, we will use a simple concept of mathematics that the product of integers is positive if
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.
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'.
'ANS' = max('ANS', 'LAST_NEG' - 'Start') [Discarding first negative integer]
'ANS'= max('ANS', 'END' - 'FRST_NEG' - 1) [Discarding last negative number]