Guys, below is the code in O(n) time complexity and O(1) Auxiliary space

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    long int N,K,p,q,sum,i,j,max=0,x=0;

    cin>>N>>K;
    long int *a=new long int[N+1]();

    for(i=0;i<K;i++)
    {
        cin>>p>>q>>sum;
        a[p]+=sum;
        if((q+1)<=N) a[q+1]-=sum;
    }

    for(i=1;i<=N;i++)
    {
       x=x+a[i];
       if(max<x) max=x;

    }

    cout<<max;
    return 0;
}

After contemplating the popular approach for solving this, here is how I wrapped my head around it.

For every input line of a-b-k, you are given the range (a to b) where the values increase by k. So instead of keeping track of actual values increasing, just keep track of the rate of change (i.e. a slope) in terms of where the rate started its increase and where it stopped its increase. This is done by adding k to the "a" position of your array and adding -k to the "b+1" position of your array for every input line a-b-k, and that's it. "b+1" is used because the increase still applied at "b".

The maximum final value is equivalent to the maximum accumulated "slope" starting from the first position, because it is the spot which incremented more than all other places. Accumulated "slope" means to you add slope changes in position 0 to position 1, then add that to position 2, and so forth, looking for the point where it was the greatest.

Java solution - passes 100% of test cases

From my HackerRank solutions.

Runtime: O(n + m)
Space Complexity: O(n)

Make sure to use long instead of int to avoid integer overflow.

Don't update all values in your array. Just update the interval's endpoint values as shown below.

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        
        /* Save interval endpoint's "k" values in array */
        long [] array = new long[N + 1];
        while (M-- > 0) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int k = scan.nextInt();
            array[a-1] += k;
            array[b]   -= k;
        }
        scan.close();
        
        /* Find max value */
        long sum = 0;
        long max = 0;
        for (int i = 0; i < N; i++) {
            sum += array[i];
            max = Math.max(max, sum);
        }
        
        System.out.println(max);
    }
}

For each of the "m" operations, we do not want to take O(n) time to process it. That's because our runtime will end up being O(nm). To get a O(n+m) runtime, we have to process each operation in O(1) time. To do so, we keep track of just the endpoints, which are just 2 numbers, instead of the O(n) numbers in between the endpoints. This is the main idea to decrease our runtime.

For a value k, we can mark its left endpoint a in the original array, along with its right endpoint b in the original array. To distinguish between a and b we can store +k for a and -k for b. Now, we technically have stored all information that the m operations represent, into an array. Most importantly, we stored it in O(m) time.

The next step is to actually find the maximum value based off of our unique representation of the data. We traverse our array from left to right. Whenever we reach a left endpoint a (which we represented with a positive number), we just add that to our sum. Whenever we reach a right endpoint b (which we represented with a negative number), we subtract that from our sum (well, technically we add a negative value). By doing so, the value sum represents the value that array[i] would have if we had applied all m operations to it. The maximum value of sum that we get while traversing the array is the value we return. If this algorithm is still unclear to you, try walking through HackerRank's Testcase 0 with the code above.

Let's try an example

Let's try to walk through an example. If we have 1 query and it wants to add 100 to elements 2 through 4 inclusive in a 7-element array, we want to have:

[0, 0, 100, 100, 100, 0, 0]

The idea is that we can represent this initially as:

[0, 0, 100, 0, 0, -100, 0]

It's important to realize that this above array is not our final answer. We will walk through the array from array[0] to array[6] to create our final answer. When we reach array[2], it basically tells us that every element from here and to the right of it (array[2] to array[6]) should have 100 added to them. When we reach array[5], it tells us the same thing, except that every element should have -100 added to it. By following these 2 rules, we get

array[0] = 0;
array[1] = 0;
array[2] = 0 + 100 = 100;
array[3] = 0 + 100 = 100;
array[4] = 0 + 100 = 100;
array[5] = 0 + 100 - 100 = 0;
array[5] = 0 + 100 - 100 = 0;

giving us the final array of

[0, 0, 100, 100, 100, 0, 0]

I hope this helps. It was challenging for me to explain.

Let me know if you have any questions.

Here's a really easy to understand python3 solution:

def arrayManipulation(n, queries):
    array = [0] * (n + 1)
    
    for query in queries: 
        a = query[0] - 1
        b = query[1]
        k = query[2]
        array[a] += k
        array[b] -= k
        
    max_value = 0
    running_count = 0
    for i in array:
        running_count += i
        if running_count > max_value:
            max_value = running_count
            
    return max_value

The idea here is to not actually access every element the query would modify as it takes up too much time. First we build an array of n+1 0's. For each query, we will add k to the value at index a - 1 (to convert to 0 indexed array), and subtract the value of k from the value at index b (this is the same as b + 1 if the array were 0 indexed which is what we want). Thus the non-zero values of the array represent how the 0s between them differ from what comes before and after.

For example if we start with this array: [0, 0, 0, 0, 0]

And our query is: (a=1, b=3, k=100)

We would modify the array to the following: [100, 0, 0, -100, 0].

The 100 tells us that its value and every value that comes after it is 100 greater than what comes before (in this case nothing, so all these values are 100). The -100, tells us that it and every value that comes after it are 100 LESS than what came before. This way we only have to perform 2 operations in O(1) time for each query, regardless of how many values it modifies.

Then to find the max value, we can simply initialize two counter variables to 0 and run through the entire array, adding each element to one of the counters and then checking to see if the number is the largest number we've seen. Then we simply return the counter with the max value we've seen. Voila!

Thanks to other commenters from whom I stole the idea. I just wanted to provide a really well explaned, high-level solution for those that are beginner programmers.

Who else thinks that the questions are not asked clearly, and hard to understand what's required?