TLE ERROR(time limit exceeded)

#1

I am doing this by brute force so its showing time limit error, How to reduce complexity??
How do i do this by binary search?

#2

Hi @bhavik911,
Take a variable which is will store maximum subarray sum which is greater than zero and if this variable has value less than 0 then making this variable as 0. Sample code

for (int i = 0; i < size; i++)  
        { 
            max_ending_here += a[i]; 

            if (max_so_far < max_ending_here)  
            { 
                max_so_far = max_ending_here; 
                start = s; 
                end = i; 
            } 

            if (max_ending_here < 0)  
            { 
                max_ending_here = 0; 
                s = i + 1; 
            } 
        }

Try solving on pen and paper to get intuition of this concept.

#3

So we have to do this using dynamic programming in this >??
Can’t we do this without that as that topic hasnt been covered yet?

#4

I do not see any use of dynamic programming for this. I have already provided you with the code required and there is no dynamic programming involved.

#5

But isnt kadanes algorithm is using dynamic ??

#6

See it is a dynamic programming problem or it is label so but in actual if you look at what dp basically is then you would not consider it as dp. As no caching or tabulation of previously-solved subproblems is necessary whereas dynamic programming, properly speaking, is when there are overlapping subproblems, and we need to cache previously-solved subproblems in order to avoid evaluating them over and over again. So if you are not well aware of dp problems, still you will not face difficulty in understanding this concept. So you may consider it as dp or not thats your choice but as you asked the question whether we require understanding of dp or not and as i already know what dp is and i assumed you had a brief idea about dp is so i wrote the statement that dp is not being used in this question. However i think you do not need dp concept to be covered to understand this problem. Hope this helps.

#7

Okay this helps , I dont have much idea about DP though :stuck_out_tongue:

#8

No issue. Happy to help :upside_down_face:

1 Like