หาตัวเลขติดต่อกันสูงสุดในอาเรย์ใน C++

เราได้รับอาเรย์จำนวนเต็มบวก เป้าหมายคือหาจำนวนตัวเลขติดต่อกัน (consecutive numbers) มากที่สุดที่มีอยู่ในอาเรย์ เริ่มจากเรียงอาเรย์ แล้วเปรียบเทียบสมาชิกติดกัน arr[j] == arr[i] + 1 (j=i+1) หากต่าง 1 เพิ่ม count และ i++,j++ มิฉะนั้น reset count=1 เก็บ max count ไว้ใน maxc

อินพุต

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

เอาต์พุต

Maximum consecutive numbers in array: 4

คำอธิบาย − เรียงแล้ว: {21,22,23,24,73,100} count=1→2→3→4 (21-24) maxc=4

อินพุต

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

เอาต์พุต

Maximum consecutive numbers in array: 4

คำอธิบาย − เรียงแล้ว: {9,11,21,41,42,43,44,61} consecutive streak ยาวสุดคือ 41-44 (4 ตัว)

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• อาเรย์ Arr[] และ n
• ฟังก์ชัน subs(int arr[], int n) คืนค่าจำนวน consecutive สูงสุด
• เรียงอาเรย์ด้วย sort(arr, arr+n)
• count=1, maxc=1
• ลูป i=0..n-2, j=i+1..n-1 ถ้า arr[j]==arr[i]+1 count++, i++ มิฉะนั้น count=1 อัปเดต maxc
• คืนค่า maxc

ตัวอย่างโค้ด

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

int subs(int arr[], int n) {
    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 << "Maximum consecutive numbers present in an array: " << subs(arr, n);
    return 0;
}

ผลลัพธ์

Maximum consecutive numbers present in an array: 10