Hiểu bài toán

Cho một dãy số nguyên A gồm N phần tử. Tìm độ dài của đoạn con liên tiếp dài nhất sao cho các phần tử trong đoạn có thứ tự không giảm (tức là aL ≤ a{L+1} ≤ ... ≤ a_H). Nếu chỉ có một phần tử, đoạn đó cũng được coi là không giảm.

Các cách tiếp cận

Cách Duyệt một lần (One-pass)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int cur = 1, ans = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] >= a[i - 1])
            cur++;
        else
            cur = 1;
        ans = max(ans, cur);
    }

    cout << ans;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là cách tiếp cận trực quan và hiệu quả nhất. Ta duyệt qua mảng từ phần tử thứ hai. Biến 'cur' lưu độ dài đoạn không giảm liên tiếp hiện tại (tính đến phần tử đang xét). Nếu phần tử hiện tại lớn hơn hoặc bằng phần tử trước đó, ta tăng 'cur' lên 1. Ngược lại, ta đặt lại 'cur' bằng 1 (bắt đầu một đoạn mới). Trong mọi trường hợp, ta cập nhật 'ans' bằng giá trị lớn nhất giữa 'ans' và 'cur'.

Cách Quy hoạch động (Dynamic Programming)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, a[100005], l[100005], maxx = 1;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(ll i = 1; i <= n; i++)
        cin >> a[i];
    for(ll i = 1; i <= n; i++){
        if(a[i] >= a[i - 1])
            l[i] = l[i - 1] + 1;
        else
            l[i] = 1;
        maxx = max(l[i], maxx);
    }
    cout << maxx;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng quy hoạch động. Ta định nghĩa mảng 'l'其中 'l[i]' là độ dài đoạn không giảm dài nhất kết thúc tại vị trí 'i'. Công thức truy hồi: 'l[i] = l[i-1] + 1' nếu 'a[i] >= a[i-1]', ngược lại 'l[i] = 1'. Sau khi tính xong mảng 'l', đáp án là giá trị lớn nhất trong mảng này. Về bản chất, giải thuật này giống với giải thuật 1 nhưng dùng thêm mảng phụ để lưu trữ kết quả của mọi vị trí, giúp trả lời các truy vấn bổ sung (nếu có).

Cách Duyệt chia mảng (Split Iteration)

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define task ""

void pre () {
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
}
/*_______________________SOLUTION IS HERE____________________________________*/

int n;
int a[100100];
int ans = 1, d = 1;
signed  main() {
    //pre();
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 2; i <= n; ++i) {
        if (a[i - 1] <= a[i]) {
            ++d;
        }
        else{
            ans = max(ans, d);
            d = 1;
        }
    }
    ans = max(ans, d);
    cout << ans;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Giải thuật này chia mảng thành các đoạn con liên tiếp không giảm. Biến 'd' đếm độ dài đoạn hiện tại. Khi gặp một sự gãy (a[i] < a[i-1]), ta kết thúc đoạn hiện tại, so sánh độ dài của nó với độ dài lớn nhất tìm được ('ans'), và reset 'd' về 1. Điểm đặc biệt là giải thuật này gọi 'max(ans, d)' một lần nữa sau vòng lặp để đảm bảo lấy được độ dài của đoạn cuối cùng (hoặc đoạn duy nhất).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể giải quyết bằng cách duyệt qua mảng một lần duy nhất.
• Vấn đề có tính chất quy hoạch động: độ dài đoạn không giảm tại vị trí i phụ thuộc vào đoạn tại vị trí i-1.
• Cần xử lý các trường hợp đặc biệt: N=1, mảng toàn phần tử bằng nhau, mảng giảm dần.

Lỗi thường gặp

• Quên kiểm tra giá trị 'ans' cuối cùng sau vòng lặp nếu giải thuật chỉ cập nhật 'ans' bên trong vòng lặp (trừ trường hợp đoạn cuối cùng).
• Sử dụng kiểu dữ liệu quá nhỏ cho các biến nếu giá trị đầu vào lớn (dù trong bài này chỉ cần int, nhưng long long an toàn hơn).
• Đọc sai yêu cầu output: chỉ cần in ra độ dài thay vì in ra đoạn con đó.