| Submit | All submissions | Best solutions | Back to list |
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
|
||||||||||
|
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 |
||||||||||
|
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... |
||||||||||
|
2020-06-03 19:50:04
easy peasy lemon squeezy ;) |
||||||||||
|
2020-05-11 09:26:53
It is giving me TLE in python |
||||||||||
|
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 ;) |
||||||||||
|
2020-02-10 14:59:04
I am getting WA in TC 13!... |
||||||||||
|
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 |
||||||||||
|
2019-12-06 18:28:03
Input: 5 1 -5 -4 5 -10 Output: 4 |
||||||||||
|
2019-09-25 21:06:44
behenchodddddd test case 15 kya babasir banai h bc!!!! |
||||||||||
|
2019-08-23 23:35:09
A little variation of LIS, use bottom up dp! (test case 15 won't bother anymore ) |
||||||||||
RSS