Given an array arr[] consisting of N integers, ( initially set to 0 ) and an array Q[], consisting of queries of the form {l, r, k}, the task for each query is to add K to the indices l to r(both inclusive). After performing all queries, return the maximum element present the array.
Example:
Input: N=10, q[] = {{1, 5, 3}, {4, 8, 7}, {6, 9, 1}}
Output: 10
Explanation:
Initially the array is ? [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Query1 {1, 5, 3} results in [3, 3, 3, 3, 3, 0, 0, 0, 0, 0]
Query2 {4, 8, 7} results in [3, 3, 3, 10, 10, 7, 7, 7, 0, 0]
Query2 {6, 9, 1} results in [3, 3, 3, 10, 10, 8, 8, 8, 1, 0]
Maximum value in the updated array = 10
Approach: Follow the steps below to solve the problem.
- Traverse over the vector of queries and for each query {l, r, k}
- Add k to a[l] and subtract k from a[r+1]
- Initialize variable x = 0 to store the running sum and m = INT_MIN to store the maximum value
- Traverse the array, add elements to x, and update m.
- Print the maximum value m
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the max sum// after processing q queriesint max_sum(int a[], vector<pair<pair<int, int>, int> > v, int q, int n){ // Store the cumulative sum int x = 0; // Store the maximum sum int m = INT_MIN; // Iterate over the range 0 to q for (int i = 0; i < q; i++) { // Variables to extract // values from vector int p, q, k; p = v[i].first.first; q = v[i].first.second; k = v[i].second; a[p] += k; if (q + 1 <= n) a[q + 1] -= k; } // Iterate over the range [1, n] for (int i = 1; i <= n; i++) { // Calculate cumulative sum x += a[i]; // Calculate maximum sum m = max(m, x); } // Return the maximum sum after q queries return m;}// Driver codeint main(){ // Stores the size of array // and number of queries int n = 10, q = 3; // Stores the sum int a[n + 5] = { 0 }; // Storing input queries vector<pair<pair<int, int>, int> > v(q); v[0].first.first = 1; v[0].first.second = 5; v[0].second = 3; v[1].first.first = 4; v[1].first.second = 8; v[1].second = 7; v[2].first.first = 6; v[2].first.second = 9; v[2].second = 1; // Function call to find the maximum sum cout << max_sum(a, v, q, n); return 0;} |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;class GFG{ // Function to find the max sum// after processing q queriesstatic int max_sum(int a[], ArrayList<ArrayList<Integer>> v, int q, int n){ // Store the cumulative sum int x = 0; // Store the maximum sum int m = Integer.MIN_VALUE; // Iterate over the range 0 to q for(int i = 0; i < q; i++) { // Variables to extract // values from vector int p, qq, k; p = v.get(i).get(0); qq = v.get(i).get(1); k = v.get(i).get(2); a[p] += k; if (qq + 1 <= n) a[qq + 1] -= k; } // Iterate over the range [1, n] for(int i = 1; i <= n; i++) { // Calculate cumulative sum x += a[i]; // Calculate maximum sum m = Math.max(m, x); } // Return the maximum sum after q queries return m;}// Driver codepublic static void main(String[] args){ // Stores the size of array // and number of queries int n = 10, q = 3; // Stores the sum int[] a = new int[n + 5]; // Storing input queries ArrayList<ArrayList<Integer>> v= new ArrayList<>(); for(int i = 0; i < q; i++) v.add(new ArrayList<>()); v.get(0).add(1); v.get(0).add(5); v.get(0).add(3); v.get(1).add(4); v.get(1).add(8); v.get(1).add(7); v.get(2).add(6); v.get(2).add(9); v.get(2).add(1); // Function call to find the maximum sum System.out.println(max_sum(a, v, q, n));}}// This code is contributed by offbeat |
Python3
# Python program for the above approach# Function to find the max sum# after processing q queriesdef max_sum(a, v, q, n): # Store the cumulative sum x = 0; # Store the maximum sum m = -10**9; # Iterate over the range 0 to q for i in range(q): # Variables to extract # values from vector p = v[i][0][0]; q = v[i][0][1]; k = v[i][1]; a[p] += k; if (q + 1 <= n): a[q + 1] -= k; # Iterate over the range [1, n] for i in range(1, n + 1): # Calculate cumulative sum x += a[i]; # Calculate maximum sum m = max(m, x); # Return the maximum sum after q queries return m;# Driver code# Stores the size of array# and number of queriesn = 10q = 3;# Stores the suma = [0] * (n + 5);# Storing input queriesv = [[[0 for i in range(2)] for x in range(2)] for z in range(q)]v[0][0][0] = 1;v[0][0][1] = 5;v[0][1] = 3;v[1][0][0] = 4;v[1][0][1] = 8;v[1][1] = 7;v[2][0][0] = 6;v[2][0][1] = 9;v[2][1] = 1;# Function call to find the maximum sumprint(max_sum(a, v, q, n));# This code is contributed by _saurabh_jaiswal |
C#
using System;using System.Collections.Generic;class GFG{ // Function to find the max sum // after processing q queries static int max_sum(int[] a, List<List<int>> v, int q, int n) { // Store the cumulative sum int x = 0; // Store the maximum sum int m = int.MinValue; // Iterate over the range 0 to q for (int i = 0; i < q; i++) { // Variables to extract // values from vector int p, qq, k; p = v[i][0]; qq = v[i][1]; k = v[i][2]; a[p] += k; if (qq + 1 <= n) a[qq + 1] -= k; } // Iterate over the range [1, n] for (int i = 1; i <= n; i++) { // Calculate cumulative sum x += a[i]; // Calculate maximum sum m = Math.Max(m, x); } // Return the maximum sum after q queries return m; } // Driver code public static void Main(string[] args) { // Stores the size of array // and number of queries int n = 10, q = 3; // Stores the sum int[] a = new int[n + 5]; // Storing input queries List<List<int>> v = new List<List<int>>(); for (int i = 0; i < q; i++) v.Add(new List<int>()); v[0].Add(1); v[0].Add(5); v[0].Add(3); v[1].Add(4); v[1].Add(8); v[1].Add(7); v[2].Add(6); v[2].Add(9); v[2].Add(1); // Function call to find the maximum sum Console.WriteLine(max_sum(a, v, q, n)); }} |
Javascript
<script>// Javascript program for the above approach// Function to find the max sum// after processing q queriesfunction max_sum(a, v, q, n) { // Store the cumulative sum let x = 0; // Store the maximum sum let m = Number.MIN_SAFE_INTEGER; // Iterate over the range 0 to q for (let i = 0; i < q; i++) { // Variables to extract // values from vector let p, q, k; p = v[i][0][0]; q = v[i][0][1]; k = v[i][1]; a[p] += k; if (q + 1 <= n) a[q + 1] -= k; } // Iterate over the range [1, n] for (let i = 1; i <= n; i++) { // Calculate cumulative sum x += a[i]; // Calculate maximum sum m = Math.max(m, x); } // Return the maximum sum after q queries return m;}// Driver code// Stores the size of array// and number of querieslet n = 10, q = 3;// Stores the sumlet a = new Array(n + 5).fill(0);// Storing input querieslet v = new Array(q).fill(0).map(() => new Array(2).fill(0).map(() => new Array(2).fill(0)));v[0][0][0] = 1;v[0][0][1] = 5;v[0][1] = 3;v[1][0][0] = 4;v[1][0][1] = 8;v[1][1] = 7;v[2][0][0] = 6;v[2][0][1] = 9;v[2][1] = 1;// Function call to find the maximum sumdocument.write(max_sum(a, v, q, n));// This code is contributed by gfgking.</script> |
Output:
10
Time Complexity: O(N+K) where N is the size of array and K is a number of queries
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
