#include "sequence.h"
#include <vector>
#include <unordered_map>
#include <queue>
#include <iostream>
using namespace std;
class SlidingWindowMedian {
public:
void add(int num) {
if (maxHeap.empty() || num <= maxHeap.top()) {
maxHeap.push(num);
} else {
minHeap.push(num);
}
balanceHeaps();
}
void remove(int num) {
if (!maxHeap.empty() && num <= maxHeap.top()) {
removedNums[num]++;
if (num == maxHeap.top()) {
removedCount++;
maxHeap.pop();
}
} else if (!minHeap.empty() && num >= minHeap.top()) {
removedNums[num]++;
if (num == minHeap.top()) {
removedCount++;
minHeap.pop();
}
}
balanceHeaps();
}
int getMedian() {
return maxHeap.top();
}
void balanceHeaps() {
while (!maxHeap.empty() && removedNums[maxHeap.top()]) {
removedCount--;
removedNums[maxHeap.top()]--;
maxHeap.pop();
}
while (!minHeap.empty() && removedNums[minHeap.top()]) {
removedCount--;
removedNums[minHeap.top()]--;
minHeap.pop();
}
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
private:
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
unordered_map<int, int> removedNums;
int removedCount = 0;
};
int sequence(int N, vector<int> A) {
int maxOccurrences = 0;
unordered_map<int, int> freq;
SlidingWindowMedian swm;
for (int l = 0; l < N; ++l) {
freq.clear();
swm = SlidingWindowMedian();
for (int r = l; r < N; ++r) {
swm.add(A[r]);
freq[A[r]]++;
int median = swm.getMedian();
maxOccurrences = max(maxOccurrences, freq[median]);
}
}
return maxOccurrences;
}
