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