Algorithm Interview Report
- 0of 0 votes
AnswersGiven a sequence of integers a[1],a[2],...,a[n], we call a sequence b[1], ..., b[m] an alternating sequence if:
- jinalshah2007 April 14, 2012 in United States
for every odd 1 < i <= m, we have b[i] < b[i-1],
for every even 1 < i <= m, we have b[i] > b[i-1].
Given a sequence of integers a[1], ..., a[n], your program must find the length of the longest alternating subsequence. (we define a[i1], ..., a[im] to be a subsequence if 1<=i1< i2<...<im<=n.)
Input
First line of input contains the length of sequence n (1<=n<=200,000). The second line contains n space seperated integers a[1], ..., a[n] (1 <= a[i] <= 10^9).
Output
Output is just a single integer number which denotes the length of longest alternating subsequence.
Sample Input
10
1 2 3 4 5 6 5 4 3 2
Sample Output
3
Explanation: On many alternating subsequences of length three, some are 1 6 2, 3 5 3, 4 6 2 etc. There is no alternating subsequence of length greater than three.
Note : A sequence with just two elements, such that the second element is greater than first is a valid alternating sequence. Moreover a sequence with only one element is also considered an alternating sequence.| Report Duplicate | Flag | PURGE
Algorithm - 0of 0 votes
AnswersWe have n punching bags in a row. Mr Lee is going to practice with them for the upcoming Boxing tournament.
- jinalshah2007 April 14, 2012 in United States
Each bag has a resistance level. Mr Lee can punch a bag if its resistance is greater than 0. He is an extremely hard puncher: when Mr Lee punches a bag, not only is its resistance set to 0 (ie: the bag is destroyed), but also the resistances of its immediately adjacent neighbors( one on left and other on right ) are decreased by one. If at any point of time the resistance of a bag drops to zero or less it is considered as destroyed. A punch on a bag with resistance greater than 0 has no impact on an immediate neighbour which is already destroyed.
Mr Lee wants to maximize his (very expensive) workout sessions, and would like to punch on these bags as much as possible. For any set of punching bags, what is the maximum number of punches that he can perform?
Input Format
On the only line of input there are n characters describing the resistances of the bags from 1 to n.
Ouput Format
On the only line of the output print an integer describing the maximum number of punches Mr Lee can punch for that set of bags.
Sample Input
11
Sample Ouput
1
Sample Input
021
Sample Output
2
Explanation
In the first example there are two bags, and we can punch only one of them before destroying both. In the second example we can punch on the third bag and then on the second bag to obtain two punches.
Constraints
Each bag has a resistance level between 0 and 3 ( inclusive ) and the number of bags is not more than 100.| Report Duplicate | Flag | PURGE
Algorithm