PROBLEM LINK:Authors: Jaub Safin DIFFICULTY:Simple PREREQUISITES:Simple observations, dp PROBLEM:An array is called alternating if any two consecutive numbers in it have opposite signs (i.e. one of them should be negative, whereas the other should be positive). You are given an array $A$ of size $N$ consisting of nonzero elements. For each index $i$ from $1$ to $N$, you have to find the length of longest subarray starting at $i$. QUICK EXPLANATION:We can observe that if an array is alternating, then all of its subarrays are also alternating. So, we can divide the array into maximal alternating subarrays. For doing that, we will iterate over array from left to right, if the sign of current number is different than previous number, then this number can be used to extend previous alternating subarray, Otherwise we will have to start constructing a new maximal alternating subarray. In this way, we can partition the array into various maximal alternating subarrays. After this, finding length of longest subarray starting at index $i$ is quite easy, as it can be done easily by finding the position of $i$ in the corresponding maximal alternating subarray. If $p$ be position and $L$ be the length of the maximal subarray, then $L  p + 1$ will be the length of longest subarray starting at index $i$. EXPLANATION:Observation 1: So, we can change the array $A$ such that it consists of 1 and 1's only. Observation 2: Let us take an example to understand how we can apply the above observation to solve the problem. Now, we go to $A_2$, we can see that $A_2, A_3, A_4$ have different signs, and $A_4$ has same sign as $A_5$. So, we break the array into several parts such that each part is maximal alternating subarray. In our example, the parts will be We can formalize the above idea to write a pseudo code to break an array into various parts of maximal alternating subarrays.
Now, let us find the length of longest alternating subarray ending at each index $i$ for our example subarray $A$. So, this means that for an maximal alternating subarray of length $L$, the answers (length of longest alternating subarray start from that index) will be $L, L1, \dots, 1$. We can use this idea to solve our problem.
Dynamic programming based SolutionYou can also solve the problem by a very simple dp. Let $len[i]$ denote the maximum length of alternating subarray starting at position $i$.
Time Complexity:As we have seen in both the solutions we have to iterate over the array $A$ only once or constant number of times. So, time complexity of the algorithm will be $\mathcal{O}(N)$ which will easily fit in time with $N = 10^5$ and $T = 10$. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 20 Mar '16, 17:34

My Approach: Everytime you find a subarray whose longest alternating count is greater than one, all you have to do is print it, and decrement and print it till it becomes one. Then skip the next count1 elements. answered 21 Mar '16, 00:18

CAn u provide us with ur test cases and corresponding answers pls.. since I am getting wrong answer . answered 21 Mar '16, 00:12

answered 21 Mar '16, 00:14

can tester tell me ur test cases and corresponding answers pls answered 21 Mar '16, 00:21
If your solution is wrong, then try generating subarrays of length <= 10 (with +1, 1) only and run against a correct solution. Also if you have some overflow bug due to not using long long at desired places, then for the same test cases, change $+1$ to $10^9$ and $1$ to $10^9$
(21 Mar '16, 07:56)
https://www.codechef.com/viewsolution/9712232 This is solution.. And not able to get any bugg
(21 Mar '16, 08:26)
Getting right answer for every sample input
(21 Mar '16, 08:28)

include <iostream>using namespace std; int main() { int t,i,j,x,k; int a[100][100]; int n[10]; x=0; cin>>t; for(i=0;i<t;i++) {="" cin="">>n[i]; for(j=0;j<n[i];j++) {="" cin="">>a[i][j]; } } for(k=0;k<t;k++) {="" for(i="0;i<n[k]1;i++)" {="" x="0;" for(j="i;j<n[k];j++)" {="" if(((a[k][j]<0)&&(a[k][j+1]="">0))((a[k][j]>0)&&(a[k][j+1]<0))) { x=x+1; } else { break; } } if(x==0) { cout<<"1"; } else { cout<<x+1; } } cout<<"1"; cout<<"\n"; } return 0; } answered 21 Mar '16, 00:22

In the dp solution why do you write answered 21 Mar '16, 00:52
There is something wrong in your claims. Can you give links of both the solutions?
(21 Mar '16, 01:10)
https://www.codechef.com/viewsolution/9713110 < this is solution where a is long long int(WA) https://www.codechef.com/viewsolution/9713154 < this is the other one(AC) The Above solutions are similar to solution in editorial https://www.codechef.com/viewsolution/9711723 < This is the one I submitted during contest.(WA) https://www.codechef.com/viewsolution/9713715 < This is with a is long long int (WA) https://www.codechef.com/viewsolution/9713162 < This is the same submission with only one change as mentioned above in previous comment(i.e. including 1ll). (AC)
(21 Mar '16, 03:08)
@dpraveen did you see the solutions above? What do you think?
(21 Mar '16, 14:16)

https://www.codechef.com/viewsolution/9712232 This is link of my solution.. getting wrong answer continuously...Still i cant found any bugg.. Pls help me out answered 21 Mar '16, 08:06
Tried inputting many cases and getting every tym correct answer.Still i am getting WA in ur compiler
(21 Mar '16, 08:09)

Did exactly the same way which is mentioned in Quick Explanation. My Solution : https://www.codechef.com/viewsolution/9708007 answered 21 Mar '16, 08:46

is my program correct? someone pl tell https://www.codechef.com/viewsolution/9714935 answered 21 Mar '16, 14:24
someone plzzzz help!!
(21 Mar '16, 14:56)
You should not print anything other than output, So remove
(21 Mar '16, 17:29)
ok.i will take care of this now. Apart frm that d program is ok na?
(21 Mar '16, 19:05)
and thanks for helping
(21 Mar '16, 19:06)
