Maximum Profit

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.

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

In the first test case, the maximum profit can be made on 4 consecutive days which are day 3,4,5,6 ( 6 + 2 - 3 + 7 = 12 ) . We can choose the consecutive elements from any range {2,4}, but we obtained max profit by considering 4 consecutive days and no other set of consecutive days gives the greater answer than 12. In the second test case, the maximum profit can be made on the 7th day (70). Not any other single day or two consecutive days gives the profit greater than or equal to 70.

In the first test case, the maximum profit can be made on the 5th day (7). Not any other single day or two/three consecutive days gives the profit greater than or equal to 7. In the second test case, the maximum profit can be made on 5 consecutive days which are day 2,3,4,5,6 (10 + 5 - 5 - 10 + 25 = 25). Here we can choose from any 2/3/4/5 consecutive days, but the max profit is given by the last 5 consecutive days.

Brute Force

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’.

Time Complexity

O(N^2), where ‘N’ is the total number of days for which profit data is maintained( length of ‘profit’).

As for every index in the size of ‘N’, we are iterating till the completion of range, which in the worst case may be of the size ‘N’. And hence due to the nesting of two loops of ‘N’ iterations each, the overall time complexity will be O(N^2).

Space Complexity

O(1).

We are not using any extra space for finding the answer. Hence, the overall space complexity is O(1).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation of sample input 1 :

Sample Input 2 :

Sample Output 2 :

Explanation for sample input 2 :