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

0 0 6 minutes read

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 zambiatek!