SPOJ.com - Problem ALTSEQ

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.

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

< Previous 1 2 3 4 5 6 7 Next >

	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 ;)
	mohaimen1: 2020-02-10 14:59:04 I am getting WA in TC 13!...
	dhairya_2000: 2019-12-07 19:56:43 AC in 1 GO :) trivial alteration of LIS problem would result in AC Last edit: 2019-12-07 19:57:35
	sandeepd: 2019-12-06 18:28:03 Input: 5 1 -5 -4 5 -10 Output: 4
	tri_cep1: 2019-09-25 21:06:44 behenchodddddd test case 15 kya babasir banai h bc!!!!
	shikhar_may7: 2019-08-23 23:35:09 A little variation of LIS, use bottom up dp! (test case 15 won't bother anymore )