Can you tell me the approach to apply dp here?

#1

this is my code which is not enough??

#2

Okay I’ll try to explain my approach.

First thing you need to know is kadane’s algo, https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/.

So this is how we will apply it over here. Consider every path as a subarray.

Now let’s say up for some node u . the path sum becomes negative, then we can be certain that if some further node makes it unstable then we should start keeping track of sum from node u onwards.
This is maintained by the cur array in my code.
So what we do is we start a bfs from root node, keep track of the sum to reach every node,
if the sum follows our constraints, we push this node in our queue otherwise we don’t.

Now for reachable node in this bfs is stable, but every unreachable has to be removed
so I do n-ans as output.

This is the code https://ide.codingblocks.com/s/295424