C++ 中 m 次范围递增操作后求数组最大值
c++server side programmingprogramming
本题中，给定一个包含 N 个元素的数组 arr[]，其初始值为 0。我们的任务是编写一个程序，用 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}
更新 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<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
