#include "sequence.h"
#include <vector>
#include <unordered_map>
#include <set>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
// Helper class to maintain the sliding window median
class SlidingWindowMedian {
public:
void insert(int num) {
if (maxHeap.empty() || num <= maxHeap.top()) {
maxHeap.push(num);
} else {
minHeap.push(num);
}
balanceHeaps();
}
void erase(int num) {
if (!maxHeap.empty() && num <= maxHeap.top()) {
delayedDeletions[num]++;
while (!maxHeap.empty() && delayedDeletions[maxHeap.top()]) {
delayedDeletions[maxHeap.top()]--;
maxHeap.pop();
}
} else {
delayedDeletions[num]++;
while (!minHeap.empty() && delayedDeletions[minHeap.top()]) {
delayedDeletions[minHeap.top()]--;
minHeap.pop();
}
}
balanceHeaps();
}
int getMedian() {
return maxHeap.top();
}
private:
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
unordered_map<int, int> delayedDeletions;
void balanceHeaps() {
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
};
int sequence(int N, vector<int> A) {
int maxOccurrences = 0;
for (int l = 0; l < N; ++l) {
unordered_map<int, int> freq;
SlidingWindowMedian swm;
for (int r = l; r < N; ++r) {
swm.insert(A[r]);
freq[A[r]]++;
int median = swm.getMedian();
maxOccurrences = max(maxOccurrences, freq[median]);
}
}
return maxOccurrences;
}
