在C ++中经过m个范围增量操作后数组中的最大值
在这个问题中，我们给了一个以0初始化的N个元素组成的数组arr[]。我们的任务是创建一个程序，以在C++中执行m个范围增量操作后在数组中找到最大值。
问题描述
在数组上，我们将执行该类型的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并从R+1中减去K。然后找到最大最大值，即为数组中的每个值更新和值，并找到操作中出现的最大值。
示例
该程序说明了我们解决方案的工作原理，
#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