考虑一个大小为n的数组，所有初始值为0。我们需要执行以下操作 M 射程增量运算。
null
increment(a, b, k) : Increment values from 'a' to 'b' by 'k'.
在m次运算之后，我们需要计算数组中的最大值。
例如：
Input : n = 5 m = 3 a = 0, b = 1, k = 100 a = 1, b = 4, k = 100 a = 2, b = 3, k = 100Output : 200Explanation:Initially array = {0, 0, 0, 0, 0}After first operation:array = {100, 100, 0, 0, 0}After second operation:array = {100, 200, 100, 100, 100}After third operation:array = {100, 200, 200, 200, 100}Maximum element after m operations is 200.Input : n = 4 m = 3 a = 1, b = 2, k = 603 a = 0, b = 0, k = 286 a = 3, b = 3, k = 882Output : 882Explanation:Initially array = {0, 0, 0, 0}After first operation:array = {0, 603, 603, 0}After second operation:array = {286, 603, 603, 0}After third operation:array = {286, 603, 603, 882}Maximum element after m operations is 882.
A. 天真法 就是在给定的范围内执行每个操作，最后找到最大值。
C++
// C++ implementation of simple approach to // find maximum value after m range increments. #include<bits/stdc++.h> using namespace std; // Function to find the maximum element after // m operations int findMax( int n, int a[], int b[], int k[], int m) { int arr[n]; memset (arr, 0, sizeof (arr)); // start performing m operations for ( int i = 0; i< m; i++) { // Store lower and upper index i.e. range int lowerbound = a[i]; int upperbound = b[i]; // Add 'k[i]' value at this operation to // whole range for ( int j=lowerbound; j<=upperbound; j++) arr[j] += k[i]; } // Find maximum value after all operations and // return int res = INT_MIN; for ( int i=0; i<n; i++) res = max(res, arr[i]); return res; } // Driver code int main() { // Number of values int n = 5; int a[] = {0, 1, 2}; int b[] = {1, 4, 3}; // value of k to be added at each operation int k[] = {100, 100, 100}; int m = sizeof (a)/ sizeof (a[0]); cout << "Maximum value after 'm' operations is " << findMax(n, a, b, k, m); return 0; } |
JAVA
// Java implementation of simple approach // to find maximum value after m range // increments. import java.util.*; class GFG{ // Function to find the maximum element after // m operations static int findMax( int n, int a[], int b[], int k[], int m) { int [] arr = new int [n]; // Start performing m operations for ( int i = 0 ; i < m; i++) { // Store lower and upper index i.e. range int lowerbound = a[i]; int upperbound = b[i]; // Add 'k[i]' value at this operation to // whole range for ( int j = lowerbound; j <= upperbound; j++) arr[j] += k[i]; } // Find maximum value after all // operations and return int res = Integer.MIN_VALUE; for ( int i = 0 ; i < n; i++) res = Math.max(res, arr[i]); return res; } // Driver Code public static void main (String[] args) { // Number of values int n = 5 ; int a[] = { 0 , 1 , 2 }; int b[] = { 1 , 4 , 3 }; // Value of k to be added at // each operation int k[] = { 100 , 100 , 100 }; int m = a.length; System.out.println( "Maximum value after 'm' " + "operations is " + findMax(n, a, b, k, m)); } } // This code is contributed by offbeat |
Python3
# Python3 program of # simple approach to # find maximum value # after m range increments. import sys # Function to find the # maximum element after # m operations def findMax(n, a, b, k, m): arr = [ 0 ] * n # Start performing m operations for i in range (m): # Store lower and upper # index i.e. range lowerbound = a[i] upperbound = b[i] # Add 'k[i]' value at # this operation to whole range for j in range (lowerbound, upperbound + 1 ): arr[j] + = k[i] # Find maximum value after # all operations and return res = - sys.maxsize - 1 for i in range (n): res = max (res, arr[i]) return res # Driver code if __name__ = = "__main__" : # Number of values n = 5 a = [ 0 , 1 , 2 ] b = [ 1 , 4 , 3 ] # Value of k to be added # at each operation k = [ 100 , 100 , 100 ] m = len (a) print ( "Maximum value after 'm' operations is " , findMax(n, a, b, k, m)) # This code is contributed by Chitranayal |
C#
// C# implementation of simple approach // to find maximum value after m range // increments. using System; public class GFG { // Function to find the maximum element after // m operations static int findMax( int n, int [] a, int [] b, int [] k, int m) { int [] arr = new int [n]; // Start performing m operations for ( int i = 0; i < m; i++) { // Store lower and upper index i.e. range int lowerbound = a[i]; int upperbound = b[i]; // Add 'k[i]' value at this operation to // whole range for ( int j = lowerbound; j <= upperbound; j++) arr[j] += k[i]; } // Find maximum value after all // operations and return int res = Int32.MinValue; for ( int i = 0; i < n; i++) res = Math.Max(res, arr[i]); return res; } // Driver Code static public void Main () { // Number of values int n = 5; int [] a = { 0, 1, 2 }; int [] b = { 1, 4, 3 }; // Value of k to be added at // each operation int [] k = { 100, 100, 100 }; int m = a.Length; Console.WriteLine( "Maximum value after 'm' " + "operations is " + findMax(n, a, b, k, m)); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript implementation of simple approach // to find maximum value after m range // increments. // Function to find the maximum element after // m operations function findMax(n, a, b, k, m) { let arr = new Array(n); arr.fill(0); // Start performing m operations for (let i = 0; i < m; i++) { // Store lower and upper index i.e. range let lowerbound = a[i]; let upperbound = b[i]; // Add 'k[i]' value at this operation to // whole range for (let j = lowerbound; j <= upperbound; j++) arr[j] += k[i]; } // Find maximum value after all // operations and return let res = Number.MIN_VALUE; for (let i = 0; i < n; i++) res = Math.max(res, arr[i]); return res; } // Number of values let n = 5; let a = [ 0, 1, 2 ]; let b = [ 1, 4, 3 ]; // Value of k to be added at // each operation let k = [ 100, 100, 100 ]; let m = a.length; document.write( "Maximum value after 'm' " + "operations is " + findMax(n, a, b, k, m)); // This code is contributed by rameshtravel07. </script> |
输出：
Maximum value after 'm' operations is 200
时间复杂性： O（米*最大值（范围））。这里的max（range）是指在一次操作中添加k的最大元素。
有效方法： 这个想法类似于 这 邮递 在一次操作中执行两件事： 1-将k值添加到范围的唯一下限。 2-将上界+1索引减少k值。 所有操作完成后，将所有值相加，检查最大和，然后打印最大和。
C++
// C++ implementation of simple approach to // find maximum value after m range increments. #include<bits/stdc++.h> using namespace std; // Function to find maximum value after 'm' operations int findMax( int n, int m, int a[], int b[], int k[]) { int arr[n+1]; memset (arr, 0, sizeof (arr)); // Start performing 'm' operations for ( int i=0; i<m; i++) { // Store lower and upper index i.e. range int lowerbound = a[i]; int upperbound = b[i]; // Add k to the lower_bound arr[lowerbound] += k[i]; // Reduce upper_bound+1 indexed value by k arr[upperbound+1] -= k[i]; } // Find maximum sum possible from all values long long sum = 0, res = INT_MIN; for ( int i=0; i < n; ++i) { sum += arr[i]; res = max(res, sum); } // return maximum value return res; } // Driver code int main() { // Number of values int n = 5; int a[] = {0, 1, 2}; int b[] = {1, 4, 3}; int k[] = {100, 100, 100}; // m is number of operations. int m = sizeof (a)/ sizeof (a[0]); cout << "Maximum value after 'm' operations is " << findMax(n, m, a, b, k); return 0; } |
JAVA
// Java implementation of // simple approach to // find maximum value after // m range increments. import java.io.*; class GFG { // Function to find maximum // value after 'm' operations static long findMax( int n, int m, int a[], int b[], int k[]) { int []arr = new int [n + 1 ]; //memset(arr, 0, sizeof(arr)); // Start performing 'm' operations for ( int i = 0 ; i < m; i++) { // Store lower and upper // index i.e. range int lowerbound = a[i]; int upperbound = b[i]; // Add k to the lower_bound arr[lowerbound] += k[i]; // Reduce upper_bound+1 // indexed value by k arr[upperbound + 1 ] -= k[i]; } // Find maximum sum // possible from all values long sum = 0 , res = Integer.MIN_VALUE; for ( int i = 0 ; i < n; ++i) { sum += arr[i]; res = Math.max(res, sum); } // return maximum value return res; } // Driver code public static void main (String[] args) { // Number of values int n = 5 ; int a[] = { 0 , 1 , 2 }; int b[] = { 1 , 4 , 3 }; int k[] = { 100 , 100 , 100 }; // m is number of operations. int m = a.length; System.out.println( "Maximum value after " + "'m' operations is " + findMax(n, m, a, b, k)); } } // This code is contributed by anuj_67. |
Python3
# Java implementation of # simple approach to # find maximum value after # m range increments. import sys def findMax(n, m, a, b, k): arr = [ 0 for i in range (n + 1 )] for i in range (m): lowerbound = a[i] upperbound = b[i] arr[lowerbound] + = k[i] arr[upperbound + 1 ] - = k[i] sum = 0 res = - 1 - sys.maxsize for i in range (n): sum + = arr[i] res = max (res, sum ) return res n = 5 a = [ 0 , 1 , 2 ] b = [ 1 , 4 , 3 ] k = [ 100 , 100 , 100 ] m = len (a) print ( "Maximum value after" , "'m' operations is" , findMax(n, m, a, b, k)) # This code is contributed by rag2127 |
C#
// c# implementation of // simple approach to // find maximum value after // m range increments. using System.Collections.Generic; using System; class GFG{ // Function to find maximum // value after 'm' operations static long findMax( int n, int m, int []a, int []b, int []k) { int []arr = new int [n + 1]; // Start performing 'm' // operations for ( int i = 0; i < m; i++) { // Store lower and upper // index i.e. range int lowerbound = a[i]; int upperbound = b[i]; // Add k to the lower_bound arr[lowerbound] += k[i]; // Reduce upper_bound+1 // indexed value by k arr[upperbound + 1] -= k[i]; } // Find maximum sum // possible from all values long sum = 0, res = -10000000; for ( int i = 0; i < n; ++i) { sum += arr[i]; res = Math.Max(res, sum); } // return maximum value return res; } // Driver code public static void Main () { // Number of values int n = 5; int []a = {0, 1, 2}; int []b = {1, 4, 3}; int []k = {100, 100, 100}; // m is number of operations. int m = a.Length; Console.WriteLine( "Maximum value after " + "'m' operations is " + findMax(n, m, a, b, k)); } } // This code is contributed by Stream_Cipher |
Javascript
<script> // Javascript implementation of // simple approach to // find maximum value after // m range increments. // Function to find maximum // value after 'm' operations function findMax(n, m, a, b, k) { let arr = new Array(n + 1); arr.fill(0); // Start performing 'm' // operations for (let i = 0; i < m; i++) { // Store lower and upper // index i.e. range let lowerbound = a[i]; let upperbound = b[i]; // Add k to the lower_bound arr[lowerbound] += k[i]; // Reduce upper_bound+1 // indexed value by k arr[upperbound + 1] -= k[i]; } // Find maximum sum // possible from all values let sum = 0, res = -10000000; for (let i = 0; i < n; ++i) { sum += arr[i]; res = Math.max(res, sum); } // return maximum value return res; } // Number of values let n = 5; let a = [0, 1, 2]; let b = [1, 4, 3]; let k = [100, 100, 100]; // m is number of operations. let m = a.length; document.write( "Maximum value after " + "'m' operations is " + findMax(n, m, a, b, k)); </script> |
输出：
Maximum value after 'm' operations is 200
时间复杂性： O（m+n）
本文由 萨希尔·查布拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
