maxLengMountain

[Problem E – Sasuke CodeWar #27]

Một dãy số gồm n phần tử gọi là dãy Mountain khi dãy đó thỏa mãn:

• a[0] < a[1] < a[2]...< a[k] > a[k+1] > ... > a[n-1].
  Với 0 < k < n-1.
• Ví dụ [1,3,5,1,0] hoặc [1,7,4,1] là dãy Mountain, còn [1,2,3] hoặc [2,2,3,4,5] không phải là dãy Mountain.

Cho một dãy a gồm các số nguyên. Hãy tìm và đưa ra dãy con dài nhất của a là dãy Mountain, nếu có nhiều dãy con dài nhất cùng độ dài thì đưa ra dãy xuất hiện trước ở trong a. Nếu không tồn tại dãy Mountain thì trả về dãy rỗng.

Ví dụ:

• Với a = [1,3,2,4,0], thì maxLengMountain(a) = [1,3,2].
  Giải thích: có 2 dãy con là dãy Mountain trong a là [1,3,2] và [2,4,0]. Kết quả trả về là dãy [1,3,2] vì dãy đó xuất hiện trước.
• Với a = [-3,5,6,0,2], thì maxLengMountain(a) = [-3,5,6,0].

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

• [Đầu vào] Arrays : Integer: a
  0 ≤ a.size() ≤ 106.
-109 ≤ a[i] ≤ 109.

• [Đầu ra] Arrays : Integer
  Dãy con dài nhất là dãy Mountain.

Author: Phan Đức Hải

Fanpage: CodeLearn.io

Group: Codelearn – Tự học lập trình C#, C++, Java, Python,Basic algorithms.