有一個城鎮有 N 棟高樓,樓高分別為 H1、H2、…、HN,市長想要在城鎮中心舉辦高空特技表演,該特技表演會從某棟大樓上朝右側滑翔至地面。
為了表演人員的安全,滑翔的路徑樓高必須越來越低,請你找出一個最長的滑翔路徑。
範例測資
範例輸入 | 範例輸出 |
---|---|
第一行有一個正整數 N (5 <= N <= 100)。 第二行有 N 個正整數 H1、H2、…、HN (1 <= Hi <= 1000)代表樓高。 | 輸出最長的滑翔路徑長度。 |
5 6 2 5 3 1 | 3 |
10 31 41 97 93 23 89 59 26 15 58 | 4 |
解題思路
收資料的時候將數字都收到一個陣列中,如果目前收到的數字非第一個數字則和陣列中前面的數值比大小。宣告一個 len 變數來存「目前遞減子區間長度」,還有一個 max 變數來存「最長遞減子區間長度」。
如果目前收到的數字比上一個數字還要小,則 len++。否則將 len = 1。每一次做這個判斷時都要和 max 做比較,如果 len > max 則 max = len。最後輸出 max 即可。
範例程式碼-ZeroJudge O076: 特技表演
#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