ซับอาร์เรย์ขนาดใหญ่ที่สุดที่มีผลรวมมากกว่า k ใน C++

โจทย์

ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมหาซับอาร์เรย์ขนาดใหญ่ที่สุดที่มีผลรวมมากกว่า k

มาดูขั้นตอนในการแก้ปัญหา

• กำหนดอาร์เรย์
• วนลูปผ่านอาร์เรย์และเก็บผลรวมที่แต่ละดัชนีในเวกเตอร์พร้อมกับดัชนี
• เรียงลำดับผลรวมข้างต้นตามผลรวมและดัชนี
• กำหนดอาร์เรย์เพื่อเก็บดัชนี
• เขียนลูปที่วนรอบจนถึง n
  • อัปเดตค่าด้วยดัชนีน้อยที่สุดของอาร์เรย์ดัชนีข้างต้นและดัชนีของอาร์เรย์ previous sums
• กำหนด sum เป็น 0
• เขียนลูปที่วนรอบจนถึง n
  • บวกองค์ประกอบปัจจุบันเข้าไปใน sum
  • ถ้า sum มากกว่า k
    • ความยาวซับอาร์เรย์สูงสุดคือ i + 1
  • มิฉะนั้นความยาวซับอาร์เรย์สูงสุดคือ
    • หาดัชนีจาก previous sums โดยใช้ binary search
    • ผลรวมที่น้อยกว่า sum - k - 1 คือดัชนีขององค์ประกอบที่เราต้องการ

ตัวอย่าง

มาดูโค้ดกัน

#include <bits/stdc++.h> 
using namespace std; 

bool compare(const pair<int, int>& a, const pair<int, int>& b) { 
    if (a.first == b.first) { 
        return a.second < b.second; 
    } 
    return a.first < b.first; 
} 

int findIndex(vector<pair<int, int> >& previousSums, int n, int val) { 
    int start = 0; 
    int end = n - 1; 
    int mid, result = -1; 
    while (start <= end) { 
        mid = (start + end) / 2; 
        if (previousSums[mid].first <= val) { 
            result = mid; 
            start = mid + 1; 
        } else { 
            end = mid - 1; 
        } 
    } 
    return result; 
} 

int getLargestSubArray(int arr[], int n, int k) { 
    int maxLength = 0; 
    vector<pair<int, int> > previousSums; 
    int sum = 0, minIndexes[n]; 
    for (int i = 0; i < n; i++) { 
        sum = sum + arr[i]; 
        previousSums.push_back({ sum, i }); 
    } 
    sort(previousSums.begin(), previousSums.end(), compare); 
    minIndexes[0] = previousSums[0].second; 
    for (int i = 1; i < n; i++) { 
        minIndexes[i] = min(minIndexes[i - 1], previousSums[i].second); 
    } 
    sum = 0; 
    for (int i = 0; i < n; i++) { 
        sum = sum + arr[i]; 
        if (sum > k) { 
            maxLength = i + 1; 
        } else { 
            int ind = findIndex(previousSums, n, sum - k - 1); 
            if (ind != -1 && minIndexes[ind] < i) { 
                maxLength = max(maxLength, i - minIndexes[ind]); 
            } 
        } 
    } 
    return maxLength; 
} 

int main() { 
    int arr[] = { 5, 3, -3, 2, 4, 7 }; 
    int k = 5, n = 6; 
    cout << getLargestSubArray(arr, n, k) << endl; 
    return 0; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้

6

สรุป

หากคุณมีคำถามในบทช่วยสอนนี้ ให้กล่าวถึงในส่วนความคิดเห็น