Giá trị lớn nhất trong mảng sau M phép tăng phạm vi trong C++

Cho mảng arr[] kích thước N khởi tạo 0. Thực hiện M phép tăng phạm vi: update[L, R, K] = cộng K vào tất cả phần tử từ L đến R. Sau M phép toán, tìm phần tử lớn nhất.

Ví dụ

Đầu vào: N = 6, M = 4, Update[][] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}}

Đầu ra: 34

Giải thích

Khởi tạo: {0, 0, 0, 0, 0, 0}
Update 1 {1,4,12}: {0, 12, 12, 12, 12, 0}
Update 2 {0,3,5}:  {5, 17, 17, 17, 12, 0}
Update 3 {1,5,7}:  {5, 24, 24, 24, 19, 7}
Update 4 {3,5,10}: {5, 24, 24, 34, 29, 17}
Max = 34

Phương pháp 1: Cập nhật trực tiếp

Cập nhật giá trị mảng cho mỗi phép toán, sau đó tìm max. Độ phức tạp O(M*N).

Ví dụ 1

#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 << "Giá trị lớn nhất sau " << M << " phép tăng phạm vi: " << findmax(arr, N);
    return 0;
}

Đầu ra

Giá trị lớn nhất trong mảng sau 4 phép tăng phạm vi là 34

Phương pháp 2: Hiệu quả hơn (O(M+N))

Thay vì lặp qua phạm vi, cộng K vào L, trừ K từ R+1. Sau đó tính tổng tiền tố và tìm max trong quá trình đó.

Ví dụ 2

#include <iostream>
using namespace std;

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

int findmax(int arr[], int N) {
    int maxVal = 0, 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 << "Giá trị lớn nhất sau " << M << " phép tăng phạm vi: " << findmax(arr, N);
    return 0;
}

Đầu ra

Giá trị lớn nhất trong mảng sau 4 phép tăng phạm vi là 34