Last Updated: 24 Apr, 2021
Maximum Profit
Moderate
Asked in companies
Mukesh is a hard worker and has a good running business. He has a list of profits he made in the last ‘N’ days. Mukesh wants to know what maximum profit he made in the few consecutive days. More Precisely he wants to know the maximum profit he made in any consecutive days in the range {‘A’, ‘B’} ( both inclusive).
You have to find the maximum profit Mukesh made in any consecutive days in the range {‘A’, ‘B’} ( both inclusive).
Note :
The profit of the Mukesh Business over ‘N’ days is shown by array/list ‘profit’. It may contain negative values as there will be a loss on those days.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain three space-separated integers ‘N’, ‘A’, ‘B’, where ‘N’ denotes the number of days for which profit data is maintained, ‘A’ denotes the lowest limit of the consecutive days to be checked and ‘B’ denotes the highest limit of the consecutive days to be checked.
The next line contains the ‘N’ space-separated integers ‘profit[i]’, where profit[i] denotes the profit on the ‘i’-th day.
Output Format :
For each test case, print the maximum possible profit that Mukesh made on any consecutive days in the range {‘A’, ‘B’}.
Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of.
Constraints :
1 <= T <= 100
1 <= N <= 2000
1 <= A <= B <= N
-100000 <= profit[i] <= 100000
Where ‘T’ is the number of test cases, 'N' is the number of days for which profit record is maintained given, ‘A’ denotes the lowest limit of the consecutive days to be checked and ‘B’ denotes the highest limit of the consecutive days to be checked and“profit[i]” is the profit on the i'th day.
Time limit: 1 sec
Approaches
The basic idea is to iterate through the given array/list ‘profit’ and check for each index as a starting point, if any possible consecutive days in the range [ ‘A’, ‘B’ ] is possible, calculate its ‘sum’ and update the ‘maxProfit’ if the ‘sum’ is greater than ‘maxProfit’ ( where ‘maxProfit’ denotes the Maximum possible profit from the array/list ‘profit’ under the given range).
Algorithm:
- Declare ‘maxProfit’ and initialize the ‘maxProfit’ with 0, where ‘maxProfit’ denotes the Maximum possible profit from the array/list ‘profit’ under the given range
- Run a loop for ‘i’ to the length of the ‘profit’ ( ‘N’ ):
- Declare ‘sum’ and initialize it with 0. Where ‘sum’ denotes the current sum starting from the index ‘i’.
- Run a loop for ‘j’ starting from ‘i’ till ‘j’ is less than the minimum of (‘i’+’B’) and ‘N’:
- Add profit[ j ] to ‘sum’.
- If j is greater than or equal to (‘i’ + ‘A’ - 1):
- update ‘maxProfit’ as ‘sum’ if ‘sum’ is greater than’maxProfit’.
- Finally, return ‘maxProfit’.
The basic idea of this approach is to check for each index as an ending point of the consecutive days. It will check for all the previous possible indexes in the range [ ‘i’-’B’, ‘i’-’A’ ]. First, build the prefix sum array/list ‘prefix’. We have the prefix sum till index ‘i’ for each of the ‘i’ from [ 0, ‘N’ ]. Now, we will iterate through the array/list ‘prefix’ starting from index ‘A’. Remove the out-of-range value from the multiset when index ‘i’ is greater than ‘B’. Then, insert the ‘prefix[i-‘A’]’ to the multiset for each index ‘i’ as it came in the minimum possible range for the current index ‘i’. Now, update the ‘maxProfit’ if the current prefix sum at index ‘i’ i.e. ‘prefix[i]’ - lowest element in the multiset ( which will be lowest in the range [ ‘i’-’B’, ‘i’-’A’ ] as B >= A ) is greater than ‘maxProfit, where ‘maxProfit’ is the maximum profit possible in the given set of days and in the given consecutive days range.
Algorithm:
- Declare the array/list ‘prefix’ and initialize ‘prefix[0]’ with 0, where ‘prefix[i]’ will store the sum from index 0 to index ‘i’ in the ‘prefix[i+1]’.
- Run a loop for ‘i’ till ‘N’:
- Assign ‘prefix[i]’ = ‘prefix[i-1]’ + ‘profit[i-1]’.
- Declare a multiset ‘mulSet’ which will store the previous possible prefix sum values of the given range.
- Run a loop for ‘i’ starting from ‘A’ till ‘N’:
- If index ‘i’ is greater than ‘B’:
- Remove the key( ‘prefix[ ‘i’ - ‘B’ - 1 ]’) from the ‘mulSet’.
- Insert the value of ‘prefix[ ‘i’ - ‘A’ ]’ to ‘mulSet’.
- Declare and initialize ‘temp’ = *’mulSet’.begin(). Here, ‘temp’ will store the minimum value present in the ‘mulSet’.
- ‘maxProfit’ = max(‘maxProfit’, ‘prefix[i]’ - temp).
- If index ‘i’ is greater than ‘B’:
- Finally, return ‘maxProfit’.