หาช่วงที่ใหญ่ที่สุดที่มีจำนวนเต็มที่กำหนด N ตัวเพียงตัวเดียวใน C++

สมมติว่ามีอาร์เรย์ของจำนวนเต็ม N ตัวที่แตกต่างกัน เราต้องหาองค์ประกอบสูงสุดในช่วง [L, R] ซึ่งช่วงนั้นมีจำนวนเต็มที่กำหนด N ตัวเพียงตัวเดียว และ 1 <= L <= R <= 10^5

ดังนั้นถ้าอาร์เรย์เป็น Arr = [5, 10, 200] ผลลัพธ์คือ 99990 ช่วงที่เป็นไปได้ทั้งหมดคือ [1, 9], [6, 199] และ [11, 100000] ช่วงสุดท้ายมีจำนวนเต็มมากที่สุดคือ 99990

แนวคิดง่ายๆ เราจะกำหนดองค์ประกอบที่เราต้องการให้ช่วงมีอยู่ ตอนนี้เราจะดูว่าสามารถขยายช่วงไปซ้ายและขวาได้อย่างไรโดยไม่ทับซ้อนกับองค์ประกอบอื่น ดังนั้นเราต้องเรียงอาร์เรย์ก่อน จากนั้นสำหรับองค์ประกอบที่กำหนด เราจะกำหนดปลายทางโดยใช้องค์ประกอบก่อนหน้าและถัดไป เราจะดูแลกรณีขอบ ดังนั้นเมื่อเรากำหนดช่วงแรกและช่วงสุดท้าย วิธีนี้สำหรับทุกองค์ประกอบ i เราหาความยาวสูงสุดของช่วง

ตัวอย่าง

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

int maximumSize(vector<int>& vec, int n) {
    vec.push_back(0);
    vec.push_back(100001);
    n += 2;
    sort(vec.begin(), vec.end());
    int max_value = 0;
    for (int i = 1; i < n - 1; i++) {
        int Left = vec[i - 1] + 1;
        int Right = vec[i + 1] - 1;
        int count = Right - Left + 1;
        max_value = max(max_value, count);
    }
    return max_value;
}

int main() {
    vector<int> v;
    v.push_back(200);
    v.push_back(10);
    v.push_back(5);
    int n = v.size();
    cout << "Maximum Size is: " << maximumSize(v, n);
}

ผลลัพธ์

Maximum Size is: 99990