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

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

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

ในอาร์เรย์ เราจะดำเนินการเพิ่มช่วง m ของประเภท

อัปเดต[L, R, K] =เพิ่มค่า K ให้กับองค์ประกอบทั้งหมดในช่วง

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

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

N =6, m =4Update[][] ={{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}} 
ผลลัพธ์
 
34
 
คำอธิบาย
 
arr[] ={0, 0, 0, 0, 0, 0}อัปเดต 1 {1, 4, 12} :arr[] ={0, 12, 12, 12, 12, 0}อัปเดต 2 { 0, 3, 5} :arr[] ={5, 17, 17, 17, 12, 0}อัปเดต 3 {1, 5, 7} :arr[] ={5, 24, 24, 24, 19, 7 }อัปเดต 4 {3, 5, 10} :arr[] ={5, 24, 24, 34, 29, 17}
 
แนวทางการแก้ปัญหา
 

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

 โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
 
#includeใช้เนมสเปซ std;int findmax(int ​​arr[], int N){ int maxVal =0; สำหรับ (int i =0; i  
ผลลัพธ์
 
ค่าสูงสุดในอาร์เรย์หลังการดำเนินการเพิ่ม 4 ช่วงคือ 34
 

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

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

 โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
 
#include โดยใช้เนมสเปซ std;int FindMaximum(int a, int b){ if(a> b) คืนค่า a; กลับข; }int findmax(int ​​arr[], int N){ int maxVal =0; ผลรวม int =0; สำหรับ (int i =0; i  
ผลลัพธ์
 
ค่าสูงสุดในอาร์เรย์หลังการดำเนินการเพิ่ม 4 ช่วงคือ 34