Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm N phần tử được khởi tạo bằng 0. Nhiệm vụ của chúng ta là tạo một chương trình để tìm Giá trị lớn nhất trong một mảng sau m các phép toán gia tăng phạm vi trong C ++.
Mô tả vấn đề
Trên mảng, chúng ta sẽ thực hiện thao tác tăng m phạm vi của kiểu,
update [L, R, K] =Thêm giá trị K vào tất cả các phần tử trong phạm vi.
Sau khi thực hiện m thao tác trên mảng. Chúng ta cần tìm phần tử có giá trị lớn nhất trong mảng.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N =6, m =4Update [] [] ={{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}} Đầu ra
34
Giải thích
arr [] ={0, 0, 0, 0, 0, 0} Cập nhật 1 {1, 4, 12}:arr [] ={0, 12, 12, 12, 12, 0} Cập nhật 2 { 0, 3, 5}:arr [] ={5, 17, 17, 17, 12, 0} Cập nhật 3 {1, 5, 7}:arr [] ={5, 24, 24, 24, 19, 7 } Cập nhật 4 {3, 5, 10}:arr [] ={5, 24, 24, 34, 29, 17} Phương pháp tiếp cận giải pháp
Một phương pháp đơn giản để giải quyết vấn đề là chỉ cần cập nhật các giá trị của mảng và sau đó sau khi tất cả các hoạt động được thực hiện. Tìm phần tử lớn nhất của mảng.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include using namespace std; int findmax (int arr [], int N) {int maxVal =0; for (int i =0; i Đầu ra
Giá trị lớn nhất trong mảng sau 4 hoạt động tăng phạm vi là 34
Thao tác này tốt nhưng lặp lại trong phạm vi cho mỗi truy vấn làm cho độ phức tạp của thứ tự O (m * N).
Một cách tiếp cận tốt hơn là thêm K vào L và trừ K khỏi R + 1 cho mỗi hoạt động gia tăng phạm vi. Và sau đó tìm giá trị lớn nhất lớn nhất, tức là cập nhật giá trị tổng cho mỗi giá trị trong mảng và tìm giá trị lớn nhất đã xảy ra trong thao tác.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include using namespace std; int FindMaximum (int a, int b) {if (a> b) return a; trả lại b; } int findmax (int arr [], int N) {int maxVal =0; int sum =0; for (int i =0; i Đầu ra
Giá trị lớn nhất trong mảng sau 4 hoạt động tăng phạm vi là 34