Chúng ta được cung cấp một mảng bất kỳ kích thước và nhiệm vụ là tìm mảng con của mảng đã cho với các phần tử có hiệu giữa các phần tử liền kề là 0 hoặc 1.
Ví dụ
Đầu vào − int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6}
Đầu ra − Độ dài mảng con tối đa với hiệu giữa các phần tử liền kề là 0 hoặc 1 là − 2
Giải thích − Các phần tử liền kề trong mảng với hiệu là 0 hoặc 1 là {2, 1}, {5, 6}, {3, 4} và {7, 6}. Do đó, độ dài tối đa của mảng con là 2.
Đầu vào − int arr[] = { 2, 1, 7, 6, 5}
Đầu ra − Độ dài mảng con tối đa với hiệu giữa các phần tử liền kề là 0 hoặc 1 là − 3
Giải thích − Các phần tử liền kề trong mảng với hiệu là 0 hoặc 1 là {2, 1} và {7, 6, 5}. Do đó, độ dài tối đa của mảng con là 3.
Phương pháp sử dụng trong chương trình dưới đây
- Nhập một mảng kiểu số nguyên có thể chứa cả phần tử dương và âm.
- Tính kích thước của mảng và truyền mảng cùng kích thước cho hàm để xử lý tiếp.
- Tạo biến tạm thời i gán 0 và biến maximum gán 0.
- Vòng lặp while từ i đến kích thước mảng.
- Trong vòng lặp, gán j = i.
- Vòng lặp while thứ hai tính toán mảng con với các phần tử liền kề có hiệu 0 hoặc 1.
- Trong vòng lặp, tăng giá trị i.
- Gán temp = i - j + 1.
- Kiểm tra nếu maximum < temp thì gán maximum = temp.
- Kiểm tra nếu j == i thì tăng i.
- Trả về maximum.
- In kết quả.
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
// Hàm tính độ dài mảng con tối đa với hiệu 0 hoặc 1 giữa các phần tử liền kề
int maximum_diff(int arr[], int size) {
int i = 0;
int maximum = 0;
while (i < size) {
int j = i;
while (i + 1 < size && (abs(arr[i] - arr[i + 1]) == 1 || abs(arr[i] - arr[i + 1]) == 0)) {
i++;
}
int temp = i - j + 1;
if (maximum < temp) {
maximum = temp;
}
if (j == i) {
i++;
}
}
return maximum;
}
int main() {
int arr[] = { 2, 1, 5, 6, 3, 4, 7, 6};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Độ dài mảng con tối đa với hiệu giữa các phần tử liền kề là 0 hoặc 1: "
<< maximum_diff(arr, size);
return 0;
}
Kết quả
Độ dài mảng con tối đa với hiệu giữa các phần tử liền kề là 0 hoặc 1: 2