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:
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 sub-sequence.

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
rushi2001: 2021-06-09 09:36:31

For Those who are getting wrong ans on testcase 15
Check this test case :
10
1 2 -9 -10 4 5 -3 -4 5 6
Expected O/P - 3

Mistake Done By people due to which they are getting wrong on 15
You have to check for every previous segment not just to the segment which is just the previous one
ie for current positive check for all previous negative segments and vice versa in case of current negative .

Last edit: 2021-06-09 09:40:20
anupam_akib: 2021-05-28 21:31:24

AC in one go!
Hints: Think about LIS problem.

Last edit: 2021-05-28 21:31:37
tr_abhishek: 2021-05-17 08:26:31

initialise all dp states with 1 and dont forget to use long long for input array. (since memset doesnt work while setting everything as anything other than 0 or -1, so for loop will work for setting dp states to 1).

you might find TC 15 annoying so take care of the return value

pratik_gl: 2021-01-13 18:37:54

Initialize all the dp states with 1. Solved the WA in Test Case 15 for me.

distructo: 2020-12-24 08:33:10

just a little variation of LIS, like literally

nfpranta: 2020-12-17 07:19:43

Check for the test case:
7
3 -4 5 -6 7 -1 9
expected output:5
this case helped me overcome error at test case 15
so the approach is for pos number try to find the max of neg increasing subsequence and viceversa

rishav0511: 2020-10-11 20:09:13

what wrong with test case 15 i m getting 2 for i/p-
5
-5 -2 4 2 -1 and
1
2
still showing WA...

pulkithb: 2020-06-03 19:50:04

easy peasy lemon squeezy ;)

vidhi_5794: 2020-05-11 09:26:53

It is giving me TLE in python

raman_111: 2020-04-26 16:59:37

if you are creating an array and initialising same time without memset that can give you WA on 15 tc

like
arr[n]={0}; -->>this will cause WA on TC 15
use memset
happy coding ;)


Added by:Beer hu !!
Date:2016-07-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Hackerrank