TLE in MAXSEGM

general
, ,
1

how can i avoid TLE in MAXSEGM without using boolean array?
kindly help!
here is link to my submission…
my submission

1 Like
2

here,i mean is it necessary to use a boolean array?

3

Yes, it is necessary to use a boolean array if you want to check the repetition of an element in constant time. Else you are going to check again and again which would increase your run time. And why do you use malloc? Please avoid using malloc if you can, because with malloc you are using heap memory which is slower. Just use declare it as int c[N]. Here you are using stack memory which is fast.

1 Like
4

it will be very helpful for me if you also elaborate a little more about boolean array ,meaning when & how to use it.

5

The Boolean array is to check if you have seen the element before. Even that will take much space. I recommend you unordered_set in c++. As you iterate through the array, check in the set if that element is there. If it is not, it is a new element, add it to running sum and insert this element into the set. However, if you find the cur element in set, it means you already seen it before. At that point check running sum with current max sum. If max is smaller, update it. Then reduce the preceding value from sum and continue. Below is my code:
https://www.codechef.com/viewsolution/14332949

6

Here, is my solution in Python. It is nearly the same logic that @sun_d mentioned in their comment. It basically stores the last seen of an item in a map which is used the next time the same number arises.