Maximum value in an array after m range increment operations
Last Updated : 06 Mar, 2025
Consider an array of size n with all initial values as 0. We need to perform the following m range increment operations.
increment(a, b, k) : Increment values from 'a' to 'b' by 'k'.
After m operations, we need to calculate the maximum of the values in the array.
Examples:
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: {100, 100, 0, 0, 0}
After second operation: {100, 200, 100, 100, 100}
After third operation {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: {0, 603, 603, 0}
After second operation: {286, 603, 603, 0}
After third operation: {286, 603, 603, 882}
Maximum element after m operations is 882.
[Naive Approach] - One by One Increment
A naive method is to perform each operation on the given range and then, at last, find the maximum number.
C++ #include <bits/stdc++.h> using namespace std; // Function to find the maximum element after // m operations int findMax(int n, vector<int>& a, vector<int>& b, vector<int>& k) { vector<int> arr(n, 0); // start performing m operations for (int i = 0; i < a.size(); 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 queries int n = 5; vector<int> a = {0, 1, 2}; vector<int> b = {1, 4, 3}; // value of k to be added at each operation vector<int> k = {100, 100, 100}; cout << "Maximum value after 'm' operations is " << findMax(n, a, b, k); return 0; } import java.util.Arrays; public class Main { // Function to find the maximum element after // m operations public static int findMax(int n, int[] a, int[] b, int[] k) { int[] arr = new int[n]; // start performing m operations for (int i = 0; i < a.length; 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 queries 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}; System.out.println("Maximum value after 'm' operations is " + findMax(n, a, b, k)); } } # Function to find the maximum element after # m operations def find_max(n, a, b, k): arr = [0] * n # start performing m operations for i in range(len(a)): # 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 = float('-inf') for i in range(n): res = max(res, arr[i]) return res # Driver code if __name__ == '__main__': # Number of queries n = 5 a = [0, 1, 2] b = [1, 4, 3] # value of k to be added at each operation k = [100, 100, 100] print("Maximum value after 'm' operations is ", find_max(n, a, b, k)) using System; using System.Linq; class Program { // Function to find the maximum element after // m operations public static int FindMax(int n, int[] a, int[] b, int[] k) { int[] arr = new int[n]; // start performing m operations for (int i = 0; i < a.Length; 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.MinValue; for (int i = 0; i < n; i++) res = Math.Max(res, arr[i]); return res; } // Driver code static void Main() { // Number of queries 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}; Console.WriteLine("Maximum value after 'm' operations is " + FindMax(n, a, b, k)); } } // Function to find the maximum element after // m operations function findMax(n, a, b, k) { let arr = new Array(n).fill(0); // start performing m operations for (let i = 0; i < a.length; 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_SAFE_INTEGER; for (let i = 0; i < n; i++) res = Math.max(res, arr[i]); return res; } // Driver code 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]; console.log("Maximum value after 'm' operations is " + findMax(n, a, b, k)); OutputMaximum value after 'm' operations is 200
Time Complexity: O(m * max(range)). Here max(range) means maximum elements to which k is added in a single operation.
Auxiliary space: O(n)
[Expected Approach] - Using Prefix Sum
The idea is similar to this post.
Perform two things in a single operation:
- Add k-value to the only lower_bound of a range.
- Reduce the upper_bound + 1 index by a k-value.
After all operations, add all values, check the maximum sum, and print the maximum sum.
C++ #include <bits/stdc++.h> using namespace std; // Function to find maximum value after 'm' operations int findMax(int n, vector<int>& a, vector<int>& b, vector<int>& k) { vector<int> arr(n + 1, 0); // Start performing 'm' operations for (int i = 0; i < a.size(); 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 if (upperbound + 1 < arr.size()) arr[upperbound + 1] -= k[i]; } // Find maximum sum possible from all values int sum = 0, res = INT_MIN; for (int i = 0; i < n; ++i) { sum += arr[i]; res = max(res, sum); } return res; } // Driver code int main() { // Number of values int n = 5; vector<int> a = {0, 1, 2}; vector<int> b = {1, 4, 3}; vector<int> k = {100, 100, 100}; cout << "Maximum value after 'm' operations is " << findMax(n, a, b, k); return 0; } // Import necessary packages import java.util.*; // Function to find maximum value after 'm' operations public class Main { public static int findMax(int n, int[] a, int[] b, int[] k) { int[] arr = new int[n + 1]; // Start performing 'm' operations for (int i = 0; i < a.length; 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 if (upperbound + 1 < arr.length) arr[upperbound + 1] -= k[i]; } // Find maximum sum possible from all values int sum = 0, res = Integer.MIN_VALUE; for (int i = 0; i < n; ++i) { sum += arr[i]; res = Math.max(res, sum); } 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}; System.out.println("Maximum value after 'm' operations is " + findMax(n, a, b, k)); } } # Function to find maximum value after 'm' operations def find_max(n, a, b, k): arr = [0] * (n + 1) # Start performing 'm' operations for i in range(len(a)): # Store lower and upper index i.e. range lowerbound = a[i] upperbound = b[i] # Add k to the lower_bound arr[lowerbound] += k[i] # Reduce upper_bound+1 indexed value by k if upperbound + 1 < len(arr): arr[upperbound + 1] -= k[i] # Find maximum sum possible from all values sum = 0 res = float('-inf') for i in range(n): sum += arr[i] res = max(res, sum) return res # Driver code if __name__ == '__main__': # Number of values n = 5 a = [0, 1, 2] b = [1, 4, 3] k = [100, 100, 100] print("Maximum value after 'm' operations is ", find_max(n, a, b, k)) // Import necessary packages using System; using System.Linq; // Function to find maximum value after 'm' operations class GfG { public static int FindMax(int n, int[] a, int[] b, int[] k) { int[] arr = new int[n + 1]; // Start performing 'm' operations for (int i = 0; i < a.Length; 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 if (upperbound + 1 < arr.Length) arr[upperbound + 1] -= k[i]; } // Find maximum sum possible from all values int sum = 0, res = int.MinValue; for (int i = 0; i < n; ++i) { sum += arr[i]; res = Math.Max(res, sum); } 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}; Console.WriteLine("Maximum value after 'm' operations is " + FindMax(n, a, b, k)); } } // Function to find maximum value after 'm' operations function findMax(n, a, b, k) { let arr = new Array(n + 1).fill(0); // Start performing 'm' operations for (let i = 0; i < a.length; 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 if (upperbound + 1 < arr.length) { arr[upperbound + 1] -= k[i]; } } // Find maximum sum possible from all values let sum = 0; let res = Number.NEGATIVE_INFINITY; for (let i = 0; i < n; i++) { sum += arr[i]; res = Math.max(res, sum); } return res; } // Driver code const n = 5; const a = [0, 1, 2]; const b = [1, 4, 3]; const k = [100, 100, 100]; console.log("Maximum value after 'm' operations is ", findMax(n, a, b, k)); OutputMaximum value after 'm' operations is 200
Time complexity: O(m + n)
Auxiliary space: O(n)
Similar Reads
For each Array index find the maximum value among all M operations Given an array arr[] of size N initially filled with 0 and another array Positions[] of size M, the task is to return the maximum value for each index after performing the following M operations: Make the value at index Positions[i] equal to 0All the numbers to the right of Positions[i] will be one
6 min read
Maximum occurred integers after M circular operations in given range Given an integer N and an array arr[] consisting of M integers from the range [1, N]. (M - 1) operations need to performed. In every ith operation, traverse every consecutive elements in the range [1, N] from arr[i] to arr[i + 1] circularly. The task is to print the most visited elements in sorted o
8 min read
Sum of Array maximums after K operations by reducing max element to its half Given an array arr[] of N integers and an integer K, the task is to find the sum of maximum of the array possible wherein each operation the current maximum of the array is replaced with its half. Example: Input: arr[] = {2, 4, 6, 8, 10}, K = 5Output: 33Explanation: In 1st operation, the maximum of
6 min read
Find maximum in an array without using Relational Operators Given an array A[] of non-negative integers, find the maximum in the array without using Relational Operator. Examples: Input : A[] = {2, 3, 1, 4, 5}Output : 5Input : A[] = {23, 17, 93}Output : 93We use repeated subtraction to find out the maximum. To find maximum between two numbers, we take a vari
9 min read
Maximum product of an Array after subtracting 1 from any element N times Given an array arr[] of positive integers of size M and an integer N, the task is to maximize the product of array after subtracting 1 from any element N number of times Examples: Input: M = 5, arr[] = {5, 1, 7, 8, 3}, N = 2Output: 630Explanation: After subtracting 1 from arr[3] 2 times, array becom
5 min read
Maximum count of values of S modulo M lying in a range [L, R] after performing given operations on the array Given an array arr[] of N integers along with integers M, L, R. Consider a variable S(initially 0). The task is to find the maximum count of values of S % M that lies in the range [L, R] after performing the following operations for each element in the given array: Add arr[i] or arr[i] - 1 to S.Chan
11 min read