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:

  • |b1| < |b2| < |b3| < ... < |bk|
  • 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

Explanation

One of the longest alternating subsequence is

     1  -2  5  -7  10

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

hide comments
2017-06-09 18:04:24
use a little variation in the LIS problem...............AC in 1 go....
2017-04-17 01:40:19 Jared León
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.
2017-04-16 14:54:57
people having WA in test case 15, beware of overflow, (in testing the sign of a number) , cost me 3 WA
2017-02-20 12:56:12
silly mistake cost me 1 WA
2017-01-24 18:54:12
Those who are failing the Test Case 15 look at the 1st condition given in problem again.(|b1|<|b2|<|b3|<.....<|bk|)
2017-01-17 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: 2017-01-17 19:31:35
2017-01-16 10:32:33 Heaven Hunter
Test case 15 giving wrong answer, does someone have any advice/tips?
Since Max(N) is 5000, I believe 32-bit integer is sufficient for storing the dp array.
2016-12-28 13:02:42
test case 15 giving wrong answer.
2016-12-25 15:25:21
max didn't cause any problem @sas
2016-12-21 23:48:56
sas pro
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.