Số liên tiếp tối đa có mặt trong mảng trong C++

Chúng ta được cho một mảng số nguyên dương. Mục tiêu là tìm số lượng số liên tiếp tối đa có mặt trong nó. Trước hết sắp xếp mảng rồi so sánh phần tử liền kề arr[j] == arr[i] + 1 (j = i + 1), nếu hiệu là 1 thì tăng count và i++, j++ ngược lại đặt count = 1. Lưu count tối đa tìm thấy cho đến nay trong maxc.

Ví dụ

Đầu vào

Arr[] = { 100, 21, 24, 73, 22, 23 }

Đầu ra

Số liên tiếp tối đa trong mảng: 4

Giải thích − Mảng sắp xếp: { 21, 22, 23, 24, 73, 100 } khởi tạo count=1, maxcount=1

1. 22 = 21+1 count=2 maxcount=2 i++,j++
2. 23 = 22+2 count=3 maxcount=3 i++,j++
3. 24 = 23+1 count=4 maxcount=4 i++,j++
4. 73 = 24+1 X count=1 maxcount=4 i++,j++
5. 100 = 73+1 X count=1 maxcount=4 i++,j++

Số liên tiếp tối đa là 4 { 21, 22, 23, 24 }.

Đầu vào

Arr[] = { 11, 41, 21, 42, 61, 43, 9, 44 }

Đầu ra

Số liên tiếp tối đa trong mảng: 4

Giải thích − Mảng sắp xếp: { 9, 11, 21, 41, 42, 43, 44, 61 } khởi tạo count=1, maxcount=1

1. 11 = 9+1 X count=1 maxcount=1 i++,j++
2. 21 = 11+1 X count=1 maxcount=1 i++,j++
3. 41 = 21+1 X count=1 maxcount=1 i++,j++
4. 42 = 41+1 count=2 maxcount=2 i++,j++
5. 43 = 42+1 count=3 maxcount=3 i++,j++
6. 44 = 43+1 count=4 maxcount=4 i++,j++
7. 61 = 44+1 X count=1 maxcount=4 i++,j++

Số liên tiếp tối đa là 4 { 41, 42, 43, 44 }.

Phương pháp sử dụng trong chương trình dưới đây

• Mảng số nguyên Arr[] lưu số.
• Số nguyên 'n' lưu độ dài mảng.
• Hàm subs(int arr[], int n) nhận mảng, kích thước, trả về số liên tiếp tối đa trong mảng.
• Đầu tiên sắp xếp mảng bằng sort(arr, arr+n).
• Khởi tạo count=1 và maxc=1.
• Bắt đầu từ hai phần tử đầu, arr[0] và arr[1] trong hai vòng for, so sánh nếu arr[j] == arr[i] + 1 (j = i+1), nếu đúng tăng count và i lên 1.
• Nếu điều kiện sai lại đặt count = 1. Cập nhật maxc với count cao nhất tìm thấy (maxc = count > maxc ? count : maxc).
• Cuối cùng trả về maxc là số phần tử liên tiếp tối đa.

Ví dụ mã nguồn

#include <iostream> 
#include <algorithm> 
using namespace std; 

int subs(int arr[], int n) { 
    std::sort(arr, arr + n); 
    int count = 1; 
    int maxc = 1; 
    for (int i = 0; i < n - 1; i++) { 
        for (int j = i + 1; j < n; j++) { 
            if (arr[j] == arr[i] + 1) { 
                count++; 
                i++; 
            } else 
                count = 1; 
            maxc = count > maxc ? count : maxc; 
        } 
    } 
    return maxc; 
} 

int main() { 
    int arr[] = { 10, 9, 8, 7, 3, 2, 1, 4, 5, 6 }; 
    int n = sizeof(arr) / sizeof(int); 
    cout << "Số liên tiếp tối đa có mặt trong mảng: " << subs(arr, n); 
    return 0; 
}

Kết quả

Số liên tiếp tối đa có mặt trong mảng: 10