Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Intuition
4.
Code
4.1.
Input
4.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Key Takeaways
Last Updated: Mar 27, 2024

Maximize Subarray Sum of Given Array by Adding X in the Range [L, R] for Q queries

Author Saksham Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Kadane algorithm is a favorite topic of interviewers, and questions are sometimes asked indirectly on it. It becomes very difficult to identify when to use this algorithm and when to not. But don’t you worry as Ninja is here to help you, and today we will see one such frequently asked question, i.e.,  maximize subarray sum of given array by adding X in the range [L, R] for Q queries which will help you to get a better grasp on the Kadane’s algorithm.

Understanding the Problem

We have been given an array of size ‘N’ and ‘M’ queries of the form (L, R, X) are also given. In each query, we will add the integer ‘X’ in the range [L, R] (starting index and ending index, respectively). Our task is to find the maximum subarray sum after each query. Let’s understand the problem better by the following example.

ARR = [4 , 2 , -11 , 4 , 5]

Queries = [[0 , 1 , 2] , [0 , 2 , -9]]

‘ARR’ after 1st query = [6 , 4 , -11 , 4 , 5]

Maximum sum subarray = [6 , 4]

Output: 10

‘ARR’ after 2nd query = [-3 , -5 , -20 , 4 , 5]

Maximum sum subarray = [4 , 5] 

Output: 9

Also see,  Rabin Karp Algorithm

Intuition

Now the idea is to make use of Kadane’s Algorithm here. We will first update the array according to the queries( in range ‘L’ to ‘R, ‘each element will be increment by ‘X’) and then use Kadane’s Algorithm to find the maximum sum subarray. Things will become more clear once you go through the code.

Code

#include <iostream>
#include <vector>
using namespace std;

// Kadane Algorithm( Read the blog for more details).
int kadane(vector<int> nums)
{
   int sum = 0;
   int maxSum = nums[0];
   for (int i = 0; i < nums.size(); i++)
   {
       sum += nums[i];
       maxSum = max(sum, maxSum);
       if (sum < 0)
           sum = 0;
   }
   return maxSum;
}

void maxSumQuery(vector<int> &arr, vector<vector<int>> &queries)
{

   for (int i = 0; i < queries.size(); i++)
   {
       // Update operation.
       for (int j = queries[i][0]; j <= queries[i][1]; j++)
       {
           arr[j] += queries[i][2];
       }

       cout << kadane(arr) << endl;
   }
}

int main()
{
   // Taking Input.
   int n;
   cin >> n;
   vector<int> arr(n, 0);
   for (int i = 0; i < n; i++)
   {
       int x;
       cin >> x;
       arr[i] = x;
   }
   int q;
   cin >> q;

   // Queries array.
   vector<vector<int> > queries(q, vector<int>(3, 0));
   for (int i = 0; i < q; i++)
   {
       int l, r, x;
       cin >> l >> r >> x;
       queries[i][0] = l;
       queries[i][1] = r;
       queries[i][2] = x;
   }

   // Calling the function.
   maxSumQuery(arr, queries);
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

5
4 2 -11 4 5
2
0 1 2
0 2 -9

Output

10
9

Time Complexity

O(M * N), where ‘M’ is the number of ‘QUERIES’ and ‘N’ is the size of the ‘ARR’.

As we are looping for ‘M’ queries and in each query, we first update the array, which will at max take O(N) time, and then apply the kadane algorithm, which also takes O(N) time. Thus time complexity = O(M) * (O(N) + O(N)) ~ O(M * N).

Space Complexity

O(1).

No extra space is used.

Key Takeaways

We saw how we could apply the Kadane algorithm to solve the problem maximize subarray sum of the given array by adding X in the range [L, R] for Q queries, which caused us O(M * N) time and O(1) space. Now, there are many other problems that can be solved using the Kadane algorithm. So what are you waiting for? Head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more. Till then, Happy Coding!

 

Live masterclass