ค่าสูงสุดในอาร์เรย์หลังการเพิ่มช่วง m ครั้งใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของ N สมาชิกที่เริ่มต้นด้วย 0 ภารกิจคือการสร้างโปรแกรมเพื่อหาค่าสูงสุดในอาร์เรย์หลังการเพิ่มช่วง (range increment) m ครั้งใน C++

คำอธิบายปัญหา

บนอาร์เรย์ เราจะดำเนินการเพิ่มช่วง m ครั้ง ประเภท:

update[L, R, K] = เพิ่มค่า K ให้กับทุกสมาชิกในช่วง

หลังจากดำเนินการ m ครั้ง เราต้องหาสมาชิกที่มีค่าสูงสุดในอาร์เรย์

ตัวอย่างเพื่อเข้าใจปัญหา:

อินพุต

N = 6, m = 4
Update[][] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}}

เอาต์พุต

34

คำอธิบาย

arr[] = {0, 0, 0, 0, 0, 0}
Update 1 {1, 4, 12} : arr[] = {0, 12, 12, 12, 12, 0}
Update 2 {0, 3, 5}  : arr[] = {5, 17, 17, 17, 12, 0}
Update 3 {1, 5, 7}  : arr[] = {5, 24, 24, 24, 19, 7}
Update 4 {3, 5, 10} : arr[] = {5, 24, 24, 34, 29, 17}

แนวทางแก้ปัญหา

วิธีง่ายคืออัปเดตค่าอาร์เรย์โดยตรงแล้วหาค่าสูงสุดหลังจบการดำเนินการทั้งหมด

ตัวอย่างโค้ด (วิธีง่าย)

#include<iostream>
using namespace std;

int findmax(int arr[], int N) {
    int maxVal = 0;
    for (int i = 0; i < N; i++) {
        if (maxVal < arr[i])
            maxVal = arr[i];
    }
    return maxVal;
}

void updateVal(int arr[], int L, int R, int K) {
    for (int i = L; i <= R; i++)
        arr[i] += K;
}

int main() {
    int N = 5;
    int arr[N] = {0};
    int M = 4;
    int rangeIncOperation[M][3] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}};
    
    for (int i = 0; i < M; i++)
        updateVal(arr, rangeIncOperation[i][0], rangeIncOperation[i][1], rangeIncOperation[i][2]);
    
    cout << "The maximum value in the array after " << M << " range increment operations is " << findmax(arr, N);
    return 0;
}

ผลลัพธ์

The maximum value in the array after 4 range increment operations is 34

วิธีนี้ดีแต่อีเกอรทช่วงสำหรับแต่ละคำถาม ทำให้ความซับซ้อนอยู่ที่ O(m*N)

วิธีที่ดีกว่าคือ เพิ่ม K ที่ L และลบ K ที่ R+1 สำหรับแต่ละการเพิ่มช่วง แล้วหาค่าสูงสุดสะสม (prefix sum maximum) นั่นคือ อัปเดตค่าสะสมสำหรับแต่ละค่าในอาร์เรย์และหาค่าสูงสุดที่เกิดขึ้นในระหว่างการดำเนินการ

ตัวอย่างโค้ด (วิธีที่ดีกว่า)

#include<iostream>
using namespace std;

int FindMaximum(int a, int b) {
    if (a > b) return a;
    return b;
}

int findmax(int arr[], int N) {
    int maxVal = 0;
    int sum = 0;
    for (int i = 0; i < N; i++) {
        sum += arr[i];
        maxVal = FindMaximum(maxVal, sum);
    }
    return maxVal;
}

void updateVal(int arr[], int L, int R, int K) {
    arr[L] += K;
    arr[R + 1] -= K;
}

int main() {
    int N = 5;
    int arr[N] = {0};
    int M = 4;
    int rangeIncOperation[M][3] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}};
    
    for (int i = 0; i < M; i++)
        updateVal(arr, rangeIncOperation[i][0], rangeIncOperation[i][1], rangeIncOperation[i][2]);
    
    cout << "The maximum value in the array after " << M << " range increment operations is " << findmax(arr, N);
    return 0;
}

ผลลัพธ์

The maximum value in the array after 4 range increment operations is 34