Maximum element present in the array after performing queries to add K to range of indices [ L , R ] | C ++ program for the above approach ; Function to find the max sum after processing q queries ; Store the cumulative sum ; Store the maximum sum ; Iterate over the range 0 to q ; Variables to extract values from vector ; Iterate over the range [ 1 , n ] ; Calculate cumulative sum ; Calculate maximum sum ; Return the maximum sum after q queries ; Driver code ; Stores the size of array and number of queries ; Stores the sum ; Storing input queries ; Function call to find the maximum sum
#include <bits/stdc++.h> NEW_LINE using namespace std ; int max_sum ( int a [ ] , vector < pair < pair < int , int > , int > > v , int q , int n ) { int x = 0 ; int m = INT_MIN ; for ( int i = 0 ; i < q ; i ++ ) { 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 ; } for ( int i = 1 ; i <= n ; i ++ ) { x += a [ i ] ; m = max ( m , x ) ; } return m ; } int main ( ) { int n = 10 , q = 3 ; int a [ n + 5 ] = { 0 } ; 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 ; cout << max_sum ( a , v , q , n ) ; return 0 ; }