MAXSEGM logic problem

general
, ,
1

Here is my code for MAXSEGM: https://pastebin.com/bi530DaB

I think there is a problem with my logic here, but I can’t figure it out,

while(l<n)
		{
			r--;
			while(r<n)
			{
				r++;
				s.insert(c[r]);
				cnt[c[r]]++;
				if(s.size()==r+1-l)
					continue;
				else
					break;
			}
			//cout<<l<<" "<<(r-1)<<endl;
			if(l>0)
				ans = tot[r-1]-tot[l-1];
			else
				ans = tot[r-1];
			//cout<<ans<<endl;
			final = max(ans,final);
			if(cnt[c[l]]==1)
				s.erase(c[l]);
			cnt[c[l]]--;
			l++;
		}

Pls help.

2

Your code fails on this test case-

Input
1
6
0 1 1 0 0 0
50 60 50 70 80 40
Your Output
150
Expected Output
120 (w[2]+2[3]=50+70 [0 based indexing] )

Working on the possible bug.

Your l and r are not getting “reset” properly. In this testcase, when, after enountering “1 1” , l and r are 1,2.

Then it encounters “0” which is not in l,r. New l and r are [2,4].Error starts from here. Next iteration, l and r become [3,5] and give wrong output for this test case.

A small log of your codes working reveals the error-

Final, l and r are 110 1 2
R is 2
R is 3
R is 4
Ans variable holds 120
Final, l and r are 120 2 4
R is 4
R is 5
Ans variable holds 150
Final, l and r are 150 3 5

I also see you got TLE in contest. You got TLE before the testcase for WA could come up. I recommend not using set for purpose of checking uniqueness, as insertion in set is a O(logN) operation, and consumes extra time.

Also, long long int takes 2x time of int. Use long long int only if you must. Some correct submissions get TLE due to over-usage of long long int.

2 Likes
3

thanks for the efforts, I will modify it accordingly.