数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
更新于: 2020年10月15日
206 次查看
广告