my solution here to the INTEG problem is giving me time limit exceeded and I cant figure out why or even give an example that produces TLE I checked the editorial and I believe I am using the approach described . pleas help! thanks.
edit: I tried running very large input and it terminates in a small time.
you have not mentioned any condition in while(1) loop for which it will break out. am i right?
yes, but I have a ‘break;’ statement that should be called when I am done with loop eventually.
yes, i just saw.
The problem with your solution is that the complexity of your solution is O(N^2) which is way more than the expected time. The expected time for the solution is O(N* Log(N)) . So just the O(N) loop which you are inserting in the middle for finding out the maximum negative value “min” can be removed if you sort the array. If the array is sorted then the negative values would come in order hence then you won’t have to find the maximum negative value again and again. So the complexity of your solution will change to O(N * log(N)) due to sorting and then O(N) for finding the cost.