Alternating Subarray Prefix

Firstly, this was not an easy problem at all, and the best part was that I passed all the Test Cases in just 1 go by taking just 25 mins including the time required to think about the idea for the problem. Now, the problem is basically based on Array iteration and maybe the knowledge of Kadane's Algorithm can help to an extent in this problem. 

I would say that the problem wants you to think about the idea that would come in most of the people's minds, but that would not pass all the Test Cases and that's the tricky part in this Problem, actually I have a little bit of experience in such problems now, and by seeing the constraints only I can tell or get an instinct that there must be something hidden in this problem that would create a problem for the Time Constraints, like in this one the input is going to a range of 10^9, generally such problems have some tricky part in which they want you to think about the optimal version of Algo that you come up with. 

         If you cannot understand this, then sorry we cannot be friends ;)

    

This problem is also difficult because firstly you need to have that basic knowledge of traversing, then coming to the basic idea part, where you have to just get the Max Size of the Subarray which must be Alternative and then another but added to this is that this is needed to be done for every element separately, and then at the end comes the tricky part, that even if you do this for every elem it won't work bcz you need to do this optimally :( 

So, overall this is like a Mario Game where you need to have a prior understanding of the hidden pits and problems in the path or else it won't be long that you will loose your 3 lives.

I have seen one thing that whatever the level of problem is, it shouldn't matter because if you think it is difficult then you just stop thinking about it bcz you have already assumed that you won't be able to solve that, and instead of this you should take it with a positive mindset and try your best to think about an idea atleast if you are not sure about the code and see if the idea you are thinking about is mentoned in the Explanation part, 1 step at a time.

So, read the Problem Statement and think that how will you get the output that is required and understand what the problem is stating and what does it want you to do.

Problem Statement:-

There's an array A consisting of N non-zero integers A1..N. A subarray of A is called alternating if any two adjacent elements in it have different signs (i.e. one of them should be negative and the other should be positive).

For each x from 1 to N, compute the length of the longest alternating subarray that starts at x - that is, a subarray Ax..y for the maximum possible y ≥ x. The length of such a subarray is y-x+1.

Input

• The first line of the input contains an integer T - the number of test cases.
• The first line of each test case contains N.
• The following line contains N space-separated integers A1..N.

Output

For each test case, output one line with N space-separated integers - the lengths of the longest alternating subarray starting at x, for each x from 1 to N.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 105
• -109 ≤ Ai ≤ 109

Sample 1:

Input

Output

3
4
1 2 3 4
4
1 -5 1 -5
6
-5 -1 -1 2 -2 -3

1 1 1 1
4 3 2 1
1 1 3 2 1 1

Explanation:

Example case 1. No two elements have different signs, so any alternating subarray may only consist of a single number.

Example case 2. Every subarray is alternating.

Example case 3. The only alternating subarray of length 3 is A3..5.

Explanation:-

To store the answers for every index I have created another array of the Name "ans" and initialized it's last elem as 1 from before only as it is always going to be 1. Then I will be having an iterator variable j which will go from 0 to second last index as the last elem is already handled. Now we will just store the size of the Subarray that is Alternative starting from x(that is current elem) in the variable count, and whenever we will get a bad condition means the subarray is not altenative anymore then we will just get out of the for loop and then use a while loop to give the next count number of elems their values of the ans array, like if we get count as 1 then only x elem will get it's count value and then we will move to the next elem normally but this while loop handles those cases where it will be optimal to use this while loop, like for example if we get the value of count for an elem as 10 so we don't have to iterate for all of the front 9 elems, instead we can use this count 10 to get their values too, I though about this because I knew that if we simply find the values individually for every elem then it would be simple but it would give an N squared Complexity and with the constraints mentioned there is no chance that it would pass the 2 secs time limit. At the end we simply print the values for every elem using the Unpacking operator(*). That's it. Peace!!

Code Implementation:-

for _ in range(int(input())):

    n=int(input())

    ints=list(map(int,input().split()))

   

    ans=[0]*n

    ans[-1]=1

    j=0

    # for j in range(size-1):

    while(j<n-1):

        # m_count=1

        count=1

        for i in range(j,n-1):

            if(ints[i]<0):

                if(ints[i+1]>0):

                    count+=1

                else:

                    # If both ints are having same sign then, just compare

                    # with m_count and

                    # update it

                    # if(count>=m_count):

                    # m_count=count

                    break

            else:

                if(ints[i+1]<0):

                    count+=1

                else:

                    # Same sign so, now check and update

                    # if(count>=m_count):

                    # m_count=count

                    break

        itr=count

        while(itr>0):

            ans[j]=itr

            j+=1

            itr-=1

           

    print(*ans)

Congrats if you made uptill here.... ;))