ALTSEQ - Alternating Sequences

Given an array a of N integers a1, a2, a3, ... aN you have to find the longest alternating sub-sequence of this array .
An alternating sequence b1, b2 ... bk, k>=1 is a sequence that has the 2 following properties:
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.


1<=N<=5000 |ai|<=10^9, ai not equal to 0.


The first line contains a single integer N, denoting the size of the array. The next line contains N integers , denoting the array a.


Print a single integer - the length of the longest alternating sub-sequence.


1 2 -2 -3 5 -7 -8 10



One of the longest alternating subsequence is 1 -2 5 -7 10

hide comments
pallindromeguy: 2018-01-14 09:17:30

Simple variation of LIS. Works in n^2. AC in one go!! :)

Last edit: 2018-01-14 09:17:44
kmkhan_014: 2017-12-10 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: 2017-12-10 19:18:49
avm5998: 2017-10-26 18:58:29

Those getting WA for TC 15,avoid using memset.It worked for me.

burninggoku: 2017-10-03 14:57:04

bas mann me LIS ko yaad rakho..sab sahi hota jaega

kshubham02: 2017-08-30 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.

TC 15 is

output should be 1.

alexandro5432: 2017-08-24 15:20:22

AC in one go...
i have used 32-bit int
no lis only dp with memorisation :)

divush: 2017-08-15 17:13:14

Use long long int if you are stuck on case 15.

deepika10: 2017-07-12 10:19:53


ankitshrey112: 2017-06-09 18:04:24

use a little variation in the LIS problem...............AC in 1 go....

Jared León: 2017-04-17 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 !!
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY