And the same approach in ruby -- I claim no credit for working this out -- I wrote this after reading the comments and code posted here.

Just thought I'd add a ruby solution for anyone looking for one.

N, M = gets.chomp.split(' ').map(&:to_i)

# create array of zeros of length N + 1
arr = Array.new(N + 1, 0)

M.times do
    # cycle through and get the inputs
    start, finish, value = gets.chomp.split(' ').map(&:to_i)

    # increment value at start of sequence
    arr[start - 1] += value

    # decrement value at first position after sequence
    arr[finish] -= value
end

tmp = 0
max = 0

arr.each do |value|
    # step through summing array
    tmp += value

    # capture the max value of tmp
    max = tmp if max < tmp
end

puts max

This worked, but I'm still trying to understand why this was the correct answer.

I would not suggest eclipsing list

Hi Vineet could u explain what logic have you followed?

Same solution but optimized:

from itertools import accumulate

n, m = map(int, input().split(' '))
dx = [0] * (n + 1) # allow run past end

for _ in range(m):
    a, b, c = map(int, input().split(' '))
    dx[a - 1] += c
    dx[b] -= c

print(max(accumulate(dx)))

How does that bottom for list return the maximum value in the list? Could you explain the logic to me please?

Why are you checking if "y" is <= len(list) ? This is given by the problem, right?

Really liked this solution! One question, shouldn't it be max=-float('inf')?

P.S - Talking about the python version

Just improved your code a bit. - split() is slightly faster than split("") - an if was not needed as always true - variables names fit those used in the exercise

if __name__ == "__main__":
    n, m = [int(n) for n in input().split()]
    l = [0]*(n+1)
    for _ in range(m):
        a, b, k = [int(n) for n in input().split()]
        l[a-1] += k
        l[b] -= k;
    max = a = 0
    for i in l:
       a+=i;
       if max<a:
            max=a;
    print(max)

I took the ideas explained here to put also into python in a bit more spelled-out way to help make sense of this more abstract work-around.

def arrayManipulation(n, queries):
        # Big O (N)
        res = [0]*(n+1) # we only really need one terminal row, since we're applying each pass to all rows below

        # loop through all the queries and apply the increments/decrements for each
        # Big O (M) (size of queires)
        for row in range(len(queries)):
                a = queries[row][0]
                b = queries[row][1]
                k = queries[row][2]

                res[a-1] += k # increment the starting position
                # this is where a loop would increment everything else between a & b by k
                # but instead of taking b-a steps, we take a constant 2 steps, saving huge on time
                res[b] -= k # decrement the position AFTER the ending position

        # now loop through res one time - Big O (N) (size of res)
        sm = 0 # running sum
        mx = 0 # maximum value found so far
        for i in range(len(res)):
                sm += res[i]
                if sm > mx:
                        mx = sm

        # total run time is Big O (2*N + M) >> Big O(N)
        return mx

The key concepts in my opinion here are:

1) we don't need to build the full aray, since it's impossible for any row but the last to have the max value. This is impossible because we apply the adjustments to every subsequent row of the resulting 2-D array.

2) we don't need to actually increment each value for indices 'a' through 'b'. While that's the most straight-forward way, that also requires x many (a minus b) steps for each pass of the loop. By noting instead where to start incrementing and where to stop incrementing (noted by decrementing after what would be the final increment), we can note the adjustments to apply without having to take every step each time. We can then run a separate single loop to go over each of the increments and keep a running sum of all the overlapping increments. The decrement allows us to know when that range where the increment applied is over by reducing the running sum by that number - in other words when that range is ended, we would have to look at overlapping increments excluding that one that just ended going forward to see if anything is bigger.

Someone else in here gave an image of a stair/hill which I found extremely helpful in visualizing and understanding this concept. The basic idea here is that instead of actually applying each increment, we can just note what the increment and range is and one by one go through each place and apply all the compounded increments at once. Loop 1 saves the increments in a different format, Loop 2 checks the overlap. And by using two separate loops we have basically Big O (N) rather than Big O (N^2) - or more specifically Big O (2N + M) instead of Big O (NM + N), where N is the size of the resulting array and M is the size of the queries array.

def arrayManipulation(n, queries): arr=[0]*n for _ in queries: start=[0]-1 end=[1]-1 val=_[2] topVal=end+1 for i in range(start,topVal): arr[i]+=val return max(arr)

m = input().split()

n = int(nm[0])

m = int(nm[1])

queries = []

for _ in range(m): queries.append(list(map(int, input().rstrip().split())))

result=arrayManipulation(n, queries)

not sure why, but when I run your code as it is I get an error: if((y)<=len(list)): list[y] -= incr; IndexError: list index out of range

but when I do run that line like this:

if((y)<=len(list)): list[y-1] -= incr;

that works

Hello, I don't really get your DIFF representation, but here is the deal:

you need to keep in mind that at the end of queries to get the real value of i we need to sum the values of A[0]->A[i].

for a query (l, r, x) if we add x to A[l] then we're sure later for every k in [l, r] sums(0->k) will include x.

the problem is that every k > r will also include that x, therefore we'll decrement l[r+1] by x.

Now the sum through 0 -> k will include x only if k >= l and will exclude it only if k > r which is equivalent to:

sum(0->k) will consider x only if k is in [l, r]

I think the DIFF matrix should be:

0    0    0    0    0
100  0    0    -100 0
0    100  0    0    0
0    0    100  0    -100

then x is 100+100+100-100-100 = 200

still don't quite get it though

As i have understood (5 , 3) 0 0 0 0 0 (1 , 2) 100 100 0 0 0 -> first and second places i.e a=1,b=2 , k=100, now a+k = 0+100 = 100, b+K = 0+100 = 100. (2 , 5) now from 2 to 5 i.e 2,3,4,5 are added with K i.e 100. already 2=100 now 2 becomes 100+100 =200, simialrly 3 = 0+100=100,4=0+100=100,5=0+100=100. (3 , 4) now 3 and 4 are added with 100. ie 3 value is 100 it becomes 100+100=200, 4 becomes 100+100=200.

among these 200 is max value.

yes ,the same with you, i am confused

you aren't allocating space for a that way. He uses new to create an array on the heap. You are trying to declare it on the stack, but you can't do that with a dynamic value like 'n'

As per my knowledge, u can create an array to size upto 10^6 in stack and for size above it we need to create in heap so we do it dynamically. https://discuss.codechef.com/questions/28604/maximum-size-of-an-array refer this

If you have a problem understanding dynamic memory then make use of vector . It allocates memory dynamically wherein the user doesn't have to deal with pointers .

vector arr(n); declares an array of long int of length n.

you can refer top coder or either gog to understand the concept of segment tree. ;)

That Made it Worse

Thank you.