Kích thước mảng con lớn nhất thỏa mãn điều kiện luân phiên trong C++

Mô tả bài toán

Cho mảng số nguyên, tìm độ dài mảng con liên tiếp dài nhất thỏa mãn một trong hai điều kiện luân phiên: 1. arr[k] > arr[k+1] khi k lẻ, arr[k] < arr[k+1] khi k chẵn. 2. arr[k] > arr[k+1] khi k chẵn, arr[k] < arr[k+1] khi k lẻ. (Hay còn gọi là mảng con "turbulent").

Giải pháp (Duyệt một lần)

• Hàm cmp(a,b) trả về 1 nếu a>b, -1 nếu a
• Duyệt mảng, duy trì anchor (đầu mảng con hiện tại).
• Nếu cmp(arr[i-1], arr[i]) == 0 → reset anchor = i.
• Nếu ở cuối mảng hoặc dấu so sánh không đổi hướng (c * cmp(arr[i], arr[i+1]) != -1) → cập nhật độ dài max, reset anchor = i.

Ví dụ minh họa

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

int cmp(int a, int b) { return (a > b) - (a < b); }

int maxSubarraySize(int arr[], int n) {
    int ans = 1, anchor = 0;
    for (int i = 1; i < n; i++) {
        int c = cmp(arr[i-1], arr[i]);
        if (c == 0) anchor = i;
        else if (i == n-1 || c * cmp(arr[i], arr[i+1]) != -1) {
            ans = max(ans, i - anchor + 1);
            anchor = i;
        }
    }
    return ans;
}

int main() {
    int arr[] = {9, 4, 2, 10, 7, 8, 8, 1, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxSubarraySize(arr, n);
    return 0;
}

Đầu ra

5