Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
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
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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!

 

Previous article
Search in a Row wise and Column wise Sorted Matrix
Next article
Aggressive Cows
Live masterclass