FOR FREE MATERIALS

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array elements between two given indices, inclusive once all operations have been performed, return the maximum value in your array.

For example 

the length of the array of zeros   n = 5, Number of queries   k = 3.     

Here in the first line, the length of the array is given, and the number of test cases.

Step 1: Let us create our array of the length which is given to us and initialize it with 0’s.

Step 2: Run a loop for the test cases.

Step 3: For the first test case.          

i.e. between 1st and 3rd position add 6

Step 4: For the end test case       

 i.e. between 2nd and 5th position add 2.

Step 5: For the final i.e. 3rd test case add 5 between 1st and 4th position.

After doing this return the max value in the array.

Time Complexity

For creating an array with the length given & initialize with 0 →  O(length)

Running a loop – O(test case)

For each value in the loop, a loop for the range starting and ending and odd the corresponding values in the given range:       O(range)

Find the max in the array and return it  O(length)

Total time: O(length) + O(test case) O(range) + O(length)

Space Complexity: O(length)

Since time complexity matters a lot in competitive coding, It may produce Time Limit Exceeded (TLE).

Better Approach

Step 1: Let us create one array of the size (length + 1) which is given to us and initialize it with 0’s.

Step 2: Run a loop for the test cases.

For the 1st test case 

 Add 6 at position 1 and subtract 6 from partition (3 + 1) i.e. 4

 For the 2nd case   

 Add 2 at partition 2 and subtract 2 from partition (5 + 1) i.e. 6

 For the final test case

 Add 5 at partition 1 and subtract 5 from partition (4 + 1) i.e. 5

Step 3: Find the Max Cumulative sum of the list and return it.