longestArrays - dãy con không giảm dài nhất

(codelearn.io - Training Easy)

Đề bài: Một dãy a được gọi là dãy không giảm nếu thỏa mãn: a[i] <= a[j] với mọi 0 <= i <  j < a.size().

Cho một mảng a gồm các số nguyên. In ra độ dài dãy con không giảm dài nhất của a.

Input: mảng a (0 < a.size() <= 10^6, a[i] <= 10^9.)
Output: Độ dài dãy con không giảm dài nhất của a.

Example:
Input: a = [3, 2, 2, 4, 6, 3].
Output: longestArrays(a) = 4.
Giải thích ví dụ: dãy con không giảm dài nhất của a trong ví dụ trên là [2, 2, 4, 6].

Chú ý: 
Ở đây ta phân biệt khái niệm dãy con tăng dài nhất và dãy con không giảm dài nhất. Hiểu đơn giản là trong dãy con tăng dài nhất thì các phần tử tăng dần từ trái qua phải và không có 2 phần tử nào trong dãy bằng nhau. 
Ở testcase mẫu, nếu yêu cầu đưa ra dãy con tăng dài nhất thì kết quả longestArrays(a) = 3, dãy con là [2, 4, 6]. Còn dãy con không giảm dài nhất theo yêu cầu của đề bài là [2, 2, 4, 6], có 2 phần tử đầu tiên trùng nhau.

Solution: Quy hoạch động cơ bản. Theo testcase mẫu thì dãy con này là dãy con liên tiếp. Gọi F[i] là độ dài dãy con tăng liên tiếp tại vị trí i, F[0] = 1 do tại vị trí 0 chỉ có 1 phần tử. Tại vị trí i, nếu a[i] >= a[i - 1] thì F[i] = F[i - 1] + 1 (độ dài dãy con tại vị trí trước đó tăng lên 1 đơn vị). Nếu không, F[i] = 1 tức là ta bắt đầu xét một dãy con mới tại vị trí i.

Công thức truy hồi:
F[0] = 1
F[i]  = max(F[i - 1] + 1, 1) nếu a[i] >= a[i - 1]

Kết quả sẽ là max(F[])

Code C++: