CodeForces/ApproximatingaConstantRange.cpp at main · codeAntariksh/CodeForces · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*
AUTHOR: Antarikshya Mitra
TIME:
PROBLEM NO:- Approximating a Constant Range 602 B
*/


#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int MOD = 1e9 + 7;

// void solve(vector<int> arr)
// {
// 	int n = arr.size();
// 	int len = -1;
// 	vector<int> pq(4,0); // (0)Max --> val, (2)Min --> val
// 	int l=0,r=0;
// 	pq[0] = arr[r];
// 	pq[2] = arr[r];
// 	pq[1] = 1;
// 	pq[3] = 1;
// 	r++;
// 	len = 1;
// 	// A O(2N) Solution
// 	while(r<n)
// 	{
// 		int newMin = min(pq[2], arr[r]);
// 		int newMax = max(pq[0], arr[r]);
// 		if(newMax - newMin <= 1)
// 		{
// 			// place(arr[r],pq);
// 			if(arr[r]==pq[0])
// 			{
// 				pq[1]++;
// 			}
// 			else pq[3]++;
// 			len = max(len,r-l+1);
// 			r++;
// 		}
// 		else
// 		{
// 			if(arr[r]>pq[2]) // New Maximum
// 			{
// 				while(pq[3]!=0)
// 				{
// 					if(arr[l]==pq[2])
// 					{
// 						pq[3]--;
// 					}
// 					if(arr[l]==pq[0])
// 						pq[1]--;
// 					l++;
// 				}
// 				// Moving Details of Maximum to Minimum
// 				pq[2] = pq[0];
// 				pq[3] = pq[1];
// 				pq[0] = arr[r];
// 				pq[1] = 1;
// 			}
// 			else
// 			{
// 				while(pq[1]!=0) // New Minimum
// 				{
// 					if(arr[l]==pq[2])
// 					{
// 						pq[3]--;
// 					}
// 					if(arr[l]==pq[0])
// 						pq[1]--;
// 					l++;
// 				}
// 				// Moving Details of Minimum to Maximum
// 				pq[0] = pq[2];
// 				pq[1] = pq[3];
// 				pq[2] = arr[r];
// 				pq[3] = 1;
// 			}
// 		}
// 	}
// 	cout<<len<<endl;
// 	return;
// }

void solve(vector<int> &arr)
{
    int n = arr.size();
    map<int,int> freq;

    int l = 0;
    int ans = 0;

    for (int r = 0; r < n; r++)
    {
        freq[arr[r]]++;

        while (freq.rbegin()->first - freq.begin()->first > 1)
        {
            freq[arr[l]]--;
            if (freq[arr[l]] == 0)
                freq.erase(arr[l]);
            l++;
        }

        ans = max(ans, r - l + 1);
    }

    cout << ans << endl;
}


int32_t main()
{
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	int n;
	cin>>n;
	vector<int> arr(n);
	for (auto &a:arr)
		cin>>a;
	solve(arr);
	return 0;
}