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.
Input: 8 1 2 -2 -3 5 -7 -8 10 Output: 5
One of the longest alternating subsequence is
1 -2 5 -7 10
There is nothing wrong with TC 15, no need of long long int, no problem with max() function, nothing wrong in SPOJ toolkit.
AC in one go...
Use long long int if you are stuck on case 15.
use a little variation in the LIS problem...............AC in 1 go....
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.
people having WA in test case 15, beware of overflow, (in testing the sign of a number) , cost me 3 WA
silly mistake cost me 1 WA
Those who are failing the Test Case 15 look at the 1st condition given in problem again.(|b1|<|b2|<|b3|<.....<|bk|)
@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