Data Modelling & AI Data Structure & Algorithm

Maximum element present in the array after performing queries to add K to range of indices [L, R]

23 June 2025

0

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 queries
int 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 code
int 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 approach
import java.lang.*;
import java.util.*;
 
class GFG{
     
// Function to find the max sum
// after processing q queries
static 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 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
    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 queries
def 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 queries
n = 10
q = 3;
 
# Stores the sum
a = [0] * (n + 5);
 
# Storing input queries
v = [[[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 sum
print(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 queries
function 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 queries
let n = 10, q = 3;
 
// Stores the sum
let a = new Array(n + 5).fill(0);
 
// Storing input queries
let 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 sum
document.write(max_sum(a, v, q, n));
 
// This code is contributed by gfgking.
</script>

Output:

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!

Maximum element present in the array after performing queries to add K to range of indices [L, R]

C++

Java

Python3

C#

Javascript

Nano Banana + Milvus: Turning Hype into Enterprise-Ready Multimodal RAG

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

LEAVE A REPLY Cancel reply

Most Popular

Samsung One UI Home: Everything you need to know

Google Play Store will call out watch faces that are hell on your battery

Nano Banana + Milvus: Turning Hype into Enterprise-Ready Multimodal RAG

T-Mobile employees push back on T-Life app asking for penny payments

EDITOR PICKS

Samsung One UI Home: Everything you need to know

Google Play Store will call out watch faces that are hell on your battery

Nano Banana + Milvus: Turning Hype into Enterprise-Ready Multimodal RAG

POPULAR POSTS

Samsung One UI Home: Everything you need to know

Google Play Store will call out watch faces that are hell on your battery

Nano Banana + Milvus: Turning Hype into Enterprise-Ready Multimodal RAG

POPULAR CATEGORY

ABOUT US

FOLLOW US