Tìm kích thước mảng con lớn nhất thỏa mãn điều kiện xen kẽ trong C++

Trong bài toán này, chúng ta được cung cấp một mảng arr[] gồm n số nguyên. Nhiệm vụ là viết chương trình tìm kích thước mảng con lớn nhất thỏa mãn điều kiện cho trước.

Mô tả bài toán

Ta cần tìm độ dài mảng con lớn nhất thỏa mãn một trong hai điều kiện:

• arr[k] > arr[k+1] nếu k lẻ và arr[k] < arr[k+1] nếu k chẵn. Với mọi phần tử của mảng con.
• arr[k] < arr[k+1] nếu k lẻ và arr[k] > arr[k+1] nếu k chẵn. Với mọi phần tử của mảng con.

Ở đây, k là chỉ số của phần tử trong mảng con (tính từ 0 trong mảng con).

Ví dụ minh họa

Đầu vào

arr[] = {7, 3, 1, 5, 4, 2, 9}

Đầu ra

4

Giải thích

Mảng con {3, 1, 5, 4} thỏa mãn điều kiện 1:
k = 1 (lẻ), arr[k] > arr[k+1], 3 > 1
k = 2 (chẵn), arr[k] < arr[k+1], 1 < 5
k = 3 (lẻ), arr[k] > arr[k+1], 5 > 4

Phương pháp giải

Từ ví dụ ta thấy: để một trong hai điều kiện đúng, mảng con phải có các phần tử xen kẽ lớn-nhỏ-lớn-nhỏ... Tức là nếu phần tử 1 > phần tử 2, thì phần tử 2 < phần tử 3, và cứ thế.

Để dễ tính toán, ta tạo mảng quan hệ chỉ ra mối quan hệ này:

• Nếu arr[i] == arr[i+1], relArr[i] = 'E'
• Nếu arr[i] > arr[i+1], relArr[i] = 'G' (Greater)
• Nếu arr[i] < arr[i+1], relArr[i] = 'S' (Smaller)

Chương trình minh họa

#include <iostream>
using namespace std;

char findRel(int a, int b) {
    if (a > b) return 'G';
    else if (a < b) return 'S';
    return 'E';
}

int calcMaxSubArray(int arr[], int n) {
    int maxLen = 1;
    int len = 1;
    char c = findRel(arr[0], arr[1]);
    
    for (int i = 1; i <= n-1; i++) {
        if (c == 'S' && findRel(arr[i], arr[i+1]) == 'G')
            len++;
        else if (c == 'G' && findRel(arr[i], arr[i+1]) == 'S')
            len++;
        else {
            if (maxLen < (len + 1))
                maxLen = (len + 1);
            len = 1;
        }
        c = findRel(arr[i], arr[i+1]);
    }
    return maxLen;
}

int main() {
    int arr[] = {7, 3, 1, 5, 4, 2, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Kích thước mảng con lớn nhất thỏa mãn điều kiện xen kẽ là "
         << calcMaxSubArray(arr, n);
    return 0;
}

Đầu ra

Kích thước mảng con lớn nhất thỏa mãn điều kiện xen kẽ là 4