In a town, there are N tall buildings with heights H1, H2, ..., HN. The mayor wants to organize a high-altitude stunt performance in the town center, where the performance will involve gliding from the top of a building toward the ground.
For the safety of the performers, the height of the buildings along the gliding path must decrease progressively. Please find the longest gliding path possible.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains a positive integer N (5 <= N <= 100).
The second line contains N positive integers H1, H2, ..., HN (1 <= Hi <= 1000) representing the heights of the buildings. | Output the length of the longest gliding path. |
| 5 6 2 5 3 1 | 3 |
| 10 31 41 97 93 23 89 59 26 15 58 | 4 |
Thought Process
When collecting data, store the numbers in an array. If the currently received number is not the first number, compare it with the previous numbers in the array. Declare a variable len to store the "current length of the decreasing subsequence" and another variable max to store the "maximum length of the decreasing subsequence".
If the currently received number is smaller than the previous number, then len++. Otherwise, set len = 1. Each time you make this comparison, compare len with max, if len > max then max = len. Finally, output max.
Sample Code－ZeroJudge O076: Performance
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vector<int>num;
int len = 1, max = -1;
for (int i = 0; i<N; i++) {
int tmp;
cin >> tmp;
num.push_back(tmp);
if (i != 0) {
if (tmp < num[i-1]) len++;
else len = 1;
if (len > max) max = len;
}
}
cout << max << "\n";
}
//ZeroJudge O076
//Dr. SeanXD