Hiểu bài toán

Bài toán yêu cầu tìm độ dài lớn nhất của một dãy con liên tiếp trong mảng mà các phần tử trong dãy có dấu xen kẽ (đan dấu). Cụ thể, nếu phần tử đầu tiên dương thì phần tử tiếp theo phải âm, sau đó lại dương, và cứ thế tiếp tục (hoặc ngược lại). Nếu không có dãy con nào thỏa mãn độ dài ít nhất 2, ta phải in ra -1. Ta cần xử lý các trường hợp đặc biệt như số 0 (vô hướng) và đảm bảo chỉ tính toán các dãy có độ dài >= 2.

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

Cách Duyệt đơn (One-pass Iteration)

#include <bits/stdc++.h>
using namespace std;
int main() {
    long n, i, d = 1, m = 1;
    cin >> n;
    long a[n];
    for (i = 0; i < n; i++) {
        cin >> a[i];
        if (i > 0 && ((a[i] > 0 && a[i-1] < 0) || (a[i] < 0 && a[i-1] > 0))) {
            d++;
            m = max(m, d);
        } else {
            d = 1;
        }
    }
    if (m == 1) cout << -1;
    else cout << m;
}

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

Đây là cách tiếp cận trực quan nhất. Ta duyệt qua mảng từ phần tử thứ 2, so sánh dấu của phần tử hiện tại với phần tử trước đó. Nếu chúng trái dấu, ta tăng độ dài dãy hiện tại lên 1 và cập nhật độ dài lớn nhất. Nếu cùng dấu (hoặc một trong hai bằng 0), ta reset độ dài dãy hiện tại về 1. Lưu ý biến d luôn khởi tạo bằng 1 khi duyệt một phần tử mới. Cuối cùng, nếu độ dài lớn nhất m vẫn là 1 nghĩa là không có dãy con nào hợp lệ, ta in -1.

Cách Quản lý trạng thái với biến phụ (State Tracking)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    long long prev, x;
    cin >> prev;
    int max_len = 0;
    int cur_len = (prev != 0) ? 1 : 0;
    for (int i = 1; i < n; i++) {
        cin >> x;
        if (x == 0) {
            cur_len = 0;
        } else if (prev * x < 0) {
            cur_len += 1;
        } else {
            cur_len = 1;
        }
        prev = x;
        max_len = max(max_len, cur_len);
    }
    cout << (max_len >= 2 ? max_len : -1);
    return 0;
}

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

Phương pháp này xử lý triệt để các trường hợp số 0. Biến cur_len theo dõi độ dài dãy con đang xét. Nếu gặp số 0, dãy con bị gián đoạn và cur_len được gán về 0. Nếu prev * x < 0, nghĩa là hai số trái dấu, ta nối phần tử mới vào dãy (cur_len++). Ngược lại (cùng dấu hoặc prev bằng 0), ta bắt đầu một dãy mới độ dài 1. Việc kiểm tra max_len >= 2 ở đầu ra giúp xử lý đúng yêu cầu in -1 nếu chỉ có dãy lẻ.

Cách Cải tiến Logic Duyệt (Optimized Iteration)

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
void Solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int ans = -1, cnt = 1;
    for (int i = 2; i <= n; ++i) {
        if (a[i] * a[i - 1] < 0) cnt++;
        else {
            ans = max(ans, cnt);
            cnt = 1;
        }
    }
    ans = max(ans, cnt);
    cout << (ans == 1 ? -1 : ans);
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    Solve();
    return 0;
}

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

Cách này tương tự Approach 1 nhưng tối ưu hơn về mặt logic đầu ra. Thay vì dùng biến m để lưu độ dài lớn nhất và so sánh m == 1 cuối cùng, nó cập nhật ans liên tục và chỉ in -1 nếu ans rốt cuộc vẫn là 1. Nó cũng sử dụng phép nhân để kiểm tra dấu (a[i] * a[i-1] < 0), giúp mã nguồn ngắn gọn hơn (lưu ý rủi ro tràn số nếu dùng int thông thường, nhưng long long trong code mẫu là an toàn).

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 trong một lần duyệt (O(n)) bằng cách chỉ cần so sánh dấu của phần tử liền trước và liền sau.
• Số 0 là một 'kẻ phá bĩnh'. Nếu gặp 0, dãy con đan dấu đang xét bị coi như kết thúc (hoặc không thể bắt đầu), vì 0 không có dấu dương hay âm.
• Độ dài dãy con chỉ thực sự có ý nghĩa nếu >= 2. Biến phụ cnt hoặc d thường được khởi tạo là 1 (đại diện cho phần tử hiện tại đang xét), và độ dài hợp lệ chỉ được ghi nhận khi có sự thay đổi dấu.

Lỗi thường gặp

• Không xử lý trường hợp N=1: Nếu chỉ có 1 phần tử, độ dài dãy con tối đa là 1, nhưng đầu ra phải là -1. Các solution trên đều xử lý đúng vì biến max_len hoặc ans sẽ không vượt quá 1.
• Tràn số khi so sánh dấu: Sử dụng phép nhân a[i] * a[i-1] để kiểm tra dấu có thể gây tràn số integer nếu giá trị quá lớn. Tuy nhiên, với giới hạn 10^5, phép nhân này an toàn nếu dùng long long.
• Lỗi truy cập mảng: Solution 1 duyệt for(i=0;...) và truy cập a[i-1]. Khi i=0, a[-1] sẽ lỗi nếu không có cơ chế kiểm soát (trong code mẫu, lỗi này có thể bị che giấu do biến i không được khởi tạo lại hoặc do cách biên dịch, nhưng về logic là sai). Solution an toàn hơn nên kiểm tra i > 0 trước khi so sánh.