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ụ của chúng ta là tạo một chương trình để tìm kích thước tối đa của mảng con thỏa mãn điều kiện đã cho.
Mô tả sự cố - Chúng ta cần tìm độ dài của mảng con lớn nhất thỏa mãn bất kỳ điều kiện nào dưới đây,
-
arr [k]> arr [k + 1], nếu k lẻ và arr [k]
-
arr [k]
arr [k + 1], nếu k chẵn. Đối với tất cả các phần tử của mảng con.
Ở đây, k là chỉ số của phần tử của mảng con trong arr [].
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {7, 3, 1, 5, 4, 2, 9} Đầu ra
4
Giải thích
The subarray {3, 1, 5, 4} satisfies the condition 1.
k = 1(odd), arr[k] > arr[k+1], 3 > 1
k = 2(even), arr[k] < arr[k+1], 1 < 5
k = 3(odd), arr[k] > arr[k+1], 5 > 4 Phương pháp tiếp cận giải pháp
Từ ví dụ, chúng ta có thể thấy rằng đối với bất kỳ điều kiện nào là đúng. Mảng con phải có các phần tử lớn hơn và nhỏ hơn thay thế, tức là nếu 1st> 2nd, rồi 2nd> 3, v.v.
Bây giờ, để tiện cho việc tính toán, chúng ta sẽ tạo một mảng quan hệ chỉ ra mối quan hệ này. Sau đây là cách chúng ta sẽ điều chỉnh mảng quan hệ,
If arr[i] == arr[i + 1],relArr[i] = ‘E’ If arr[i] > arr[i + 1],relArr[i] = ‘G’ If arr[i] < arr[i + 1],relArr[i] = ‘S’
Sử dụng mảng này, chúng ta có thể dễ dàng tìm thấy kích thước tối đa của mảng con. Mảng con được xem xét sẽ có ‘G’ và ‘S’ thay thế.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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<<"The maximum size of sub−array that satisfies the given
condition is "<<calcMaxSubArray(arr, n);
} Đầu ra
The maximum size of sub-array that satisfies the given condition is 4