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