算法（m个范围增量操作后数组中的最大值） _删除指定范围的数组元素

本文概述

C++
Java
Python3
C ++
Java

考虑一个大小为n的数组，所有初始值都为0，我们需要执行以下m个范围递增操作。

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 = 100 Output : 200 Explanation: 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 = 882 Output : 882 Explanation: 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.

一种天真的方法是在给定范围内执行每个操作, 然后最后找到最大数量。
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 progrma 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 - 1for 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

输出如下：

Maximum value after 'm' operations is 200

时间复杂度：O(m * max(range))。此处的max(range)表示在单个操作中将k添加到的最大元素。
高效的方法：
这个想法类似于
这个
【算法（m个范围增量操作后数组中的最大值）】发布。
只需一次操作即可完成两件事：
1-将k值添加到范围的lower_bound。
2-通过k值减少upper_bound +1索引。
毕竟, 进行操作, 将所有值相加, 检查最大和, 然后打印最大和。
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.

输出如下：