ALTSEQ  Alternating Sequences
Given an array a of N integers a1, a2, a3, ... aN you have to find the longest alternating subsequence of this array .
An alternating sequence b1, b2 ... bk, k>=1 is a sequence that has the 2 following properties:
1.b1<b2<b3<.....<bk
2. The signs alternate between adjacent elements, i.e, if b1 > 0 then b2<0, b3 >0 and so on. Alternatively, if b1<0, then b2>0, b3<0 and so on.
A sub sequence of array a is a sequence obtained by dropping some elements of the array a.
Here is the formal definition.
It is guaranteed that the array a contains no element equal to 0.
Constraints
1<=N<=5000 ai<=10^9, ai not equal to 0.
Input
The first line contains a single integer N, denoting the size of the array. The next line contains N integers , denoting the array a.
Output
Print a single integer  the length of the longest alternating subsequence.
Example
Input: 8 1 2 2 3 5 7 8 10 Output: 5
Explaination
One of the longest alternating subsequence is 1 2 5 7 10
hide comments
kshubham02:
20170830 12:49:41
There is nothing wrong with TC 15, no need of long long int, no problem with max() function, nothing wrong in SPOJ toolkit.


alexandro5432:
20170824 15:20:22
AC in one go...


divush:
20170815 17:13:14
Use long long int if you are stuck on case 15. 

deepika10:
20170712 10:19:53
Easy! 

ankitshrey112:
20170609 18:04:24
use a little variation in the LIS problem...............AC in 1 go.... 

Jared León:
20170417 01:40:19
No need for long long in c++. Somehow it gets crazy when the condition ( ai > aj and (ai > 0 and aj < 0 ) or (ai < 0 and aj>0) ) is used. Instead, the bug free condition (ai > 0 and aj < 0 and ai > aj) or (ai < 0 and aj > 0 and ai > aj) is necessary. Most WA in test case 15 are because of bugs and not the algorithm itself. 

ahmedcpbl:
20170416 14:54:57
people having WA in test case 15, beware of overflow, (in testing the sign of a number) , cost me 3 WA 

vengatesh15:
20170220 12:56:12
silly mistake cost me 1 WA 

themast3r:
20170124 18:54:12
Those who are failing the Test Case 15 look at the 1st condition given in problem again.(b1<b2<b3<.....<bk) 

aimbot:
20170117 19:30:17
@heavenhunter  My tip is to not use spoj toolkit, there are bad test cases there, I modified my code according to that and got a lot of WA (mostly on test 15). And yes, int is enough to hold the array. (I just set the size of dp to 5005 or something a little more than 5000 just in case) Last edit: 20170117 19:31:35 
Added by:  Beer hu !! 
Date:  20160701 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Hackerrank 