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
pallindromeguy:
20180114 09:17:30
Simple variation of LIS. Works in n^2. AC in one go!! :) Last edit: 20180114 09:17:44 

kmkhan_014:
20171210 19:18:06
when checking the condition if ai and aj have opposite signs use !(ai > 0 && aj > 0) and not ai*aj < 0. When using the latter make sure to typecaste the product into long long. Last edit: 20171210 19:18:49 

avm5998:
20171026 18:58:29
Those getting WA for TC 15,avoid using memset.It worked for me. 

burninggoku:
20171003 14:57:04
bas mann me LIS ko yaad rakho..sab sahi hota jaega 

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. 
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 