資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告