Given an array arr[] of N integers and M update queries of the type (L, R, X), the task is to find the maximum subarray sum after each update query where in each query, add integer X to every element of the array arr[] in the range [L, R].
Examples:
Input: arr[] = {-1, 5, -2, 9, 3, -3, 2}, query[] = {{0, 2, -10}, {4, 5, 2}}
Output: 12 15
Explanation: Below are the steps to solve the above example:
- The array after 1st update query becomes arr[] = {-11, -5, -12, 9, 3, -3, 2}. Hence the maximum subarray sum is 12 of the subarray arr[3… 4].
- The array after 2nd update query becomes arr[] = {-11, -5, -12, 9, 5, -1, 2}. Hence the maximum subarray sum is 15 of the subarray arr[3… 6].
Input: arr[] = {-2, -5, 6, -2, -3, 1, 5, -6, 4, -1}, query[] = {{1, 4, 3}, {4, 5, -4}, {7, 9, 5}}
Output: 16 10 20
Approach: The given problem can be solved using Kadane’s Algorithm. For each query, update the array elements by traversing over all the elements of the array arr[] in the range [L, R] and add integer X to each element. After every update query, calculate the maximum subarray sum using the algorithm discussed here.
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 maximum subarray// sum using Kadane's Algorithmint maxSubarraySum(int arr[], int n){ // Stores the maximum sum int maxSum = INT_MIN; int currSum = 0; // Loop to iterate over the array for (int i = 0; i <= n - 1; i++) { currSum += arr[i]; // Update maxSum if (currSum > maxSum) { maxSum = currSum; } if (currSum < 0) { currSum = 0; } } // Return Answer return maxSum;}// Function to add integer X to all elements// of the given array in range [L, R]void updateArr(int* arr, int L, int R, int X){ // Loop to iterate over the range for (int i = L; i <= R; i++) { arr[i] += X; }}// Function to find the maximum subarray sum// after each range update queryvoid maxSubarraySumQuery( int arr[], int n, vector<vector<int> > query){ // Loop to iterate over the queries for (int i = 0; i < query.size(); i++) { // Function call to update the array // according to the mentioned query updateArr(arr, query[i][0], query[i][1], query[i][2]); // Print the max subarray sum after // updating the given array cout << maxSubarraySum(arr, n) << " "; }}// Driver Codeint main(){ int arr[] = { -2, -5, 6, -2, -3, 1, 5, -6, 4, -1 }; int N = sizeof(arr) / sizeof(arr[0]); vector<vector<int> > query{ { 1, 4, 3 }, { 4, 5, -4 }, { 7, 9, 5 } }; maxSubarraySumQuery(arr, N, query); return 0;} |
Java
// Java program for the above approachclass GFG { // Function to find the maximum subarray // sum using Kadane's Algorithm public static int maxSubarraySum(int arr[], int n) { // Stores the maximum sum int maxSum = Integer.MIN_VALUE; int currSum = 0; // Loop to iterate over the array for (int i = 0; i <= n - 1; i++) { currSum += arr[i]; // Update maxSum if (currSum > maxSum) { maxSum = currSum; } if (currSum < 0) { currSum = 0; } } // Return Answer return maxSum; } // Function to add integer X to all elements // of the given array in range [L, R] public static void updateArr(int[] arr, int L, int R, int X) { // Loop to iterate over the range for (int i = L; i <= R; i++) { arr[i] += X; } } // Function to find the maximum subarray sum // after each range update query public static void maxSubarraySumQuery(int arr[], int n, int[][] query) { // Loop to iterate over the queries for (int i = 0; i < query.length; i++) { // Function call to update the array // according to the mentioned query updateArr(arr, query[i][0], query[i][1], query[i][2]); // Print the max subarray sum after // updating the given array System.out.print(maxSubarraySum(arr, n) + " "); } } // Driver Code public static void main(String args[]) { int arr[] = { -2, -5, 6, -2, -3, 1, 5, -6, 4, -1 }; int N = arr.length; int[][] query = { { 1, 4, 3 }, { 4, 5, -4 }, { 7, 9, 5 } }; maxSubarraySumQuery(arr, N, query); }}// This code is contributed by saurabh_jaiswal. |
Python3
# Python Program to implement# the above approach# Function to find the maximum subarray# sum using Kadane's Algorithmdef maxSubarraySum(arr, n): # Stores the maximum sum maxSum = 10 ** -9 currSum = 0 # Loop to iterate over the array for i in range(n): currSum += arr[i] # Update maxSum if (currSum > maxSum): maxSum = currSum if (currSum < 0): currSum = 0 # Return Answer return maxSum# Function to add integer X to all elements# of the given array in range[L, R]def updateArr(arr, L, R, X): # Loop to iterate over the range for i in range(L, R + 1): arr[i] += X# Function to find the maximum subarray sum# after each range update querydef maxSubarraySumQuery(arr, n, query): # Loop to iterate over the queries for i in range(len(query)): # Function call to update the array # according to the mentioned query updateArr(arr, query[i][0], query[i][1], query[i][2]) # Print the max subarray sum after # updating the given array print(maxSubarraySum(arr, n), end=" ")# Driver Codearr = [-2, -5, 6, -2, -3, 1, 5, -6, 4, -1]N = len(arr)query = [[1, 4, 3],[4, 5, -4],[7, 9, 5]]maxSubarraySumQuery(arr, N, query)# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum subarray // sum using Kadane's Algorithm public static int maxSubarraySum(int[] arr, int n) { // Stores the maximum sum int maxSum = int.MinValue; int currSum = 0; // Loop to iterate over the array for (int i = 0; i <= n - 1; i++) { currSum += arr[i]; // Update maxSum if (currSum > maxSum) { maxSum = currSum; } if (currSum < 0) { currSum = 0; } } // Return Answer return maxSum; } // Function to add integer X to all elements // of the given array in range [L, R] public static void updateArr(int[] arr, int L, int R, int X) { // Loop to iterate over the range for (int i = L; i <= R; i++) { arr[i] += X; } } // Function to find the maximum subarray sum // after each range update query public static void maxSubarraySumQuery(int[] arr, int n, int[,] query) { // Loop to iterate over the queries for (int i = 0; i < query.Length; i++) { // Function call to update the array // according to the mentioned query updateArr(arr, query[i, 0], query[i, 1], query[i, 2]); // Print the max subarray sum after // updating the given array Console.Write(maxSubarraySum(arr, n) + " "); } } // Driver Code public static void Main() { int[] arr = { -2, -5, 6, -2, -3, 1, 5, -6, 4, -1 }; int N = arr.Length; int[,] query = { { 1, 4, 3 }, { 4, 5, -4 }, { 7, 9, 5 } }; maxSubarraySumQuery(arr, N, query); }}// This code is contributed by _saurabh_jaiswal. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the maximum subarray // sum using Kadane's Algorithm function maxSubarraySum(arr, n) { // Stores the maximum sum let maxSum = Number.MIN_VALUE; let currSum = 0; // Loop to iterate over the array for (let i = 0; i <= n - 1; i++) { currSum += arr[i]; // Update maxSum if (currSum > maxSum) { maxSum = currSum; } if (currSum < 0) { currSum = 0; } } // Return Answer return maxSum; } // Function to add integer X to all elements // of the given array in range [L, R] function updateArr(arr, L, R, X) { // Loop to iterate over the range for (let i = L; i <= R; i++) { arr[i] += X; } } // Function to find the maximum subarray sum // after each range update query function maxSubarraySumQuery( arr, n, query) { // Loop to iterate over the queries for (let i = 0; i < query.length; i++) { // Function call to update the array // according to the mentioned query updateArr(arr, query[i][0], query[i][1], query[i][2]); // Print the max subarray sum after // updating the given array document.write(maxSubarraySum(arr, n) + " "); } } // Driver Code let arr = [-2, -5, 6, -2, -3, 1, 5, -6, 4, -1]; let N = arr.length; let query = [[1, 4, 3], [4, 5, -4], [7, 9, 5]]; maxSubarraySumQuery(arr, N, query);// This code is contributed by Potta Lokesh</script> |
Output
16 10 20
Time Complexity: O(N*M)
Auxiliary Space: 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!
