在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