점근선 계산 - 9
Задача
아래 코드의 경우 점근선을 찾으십시오.
#include <bits/stdc++.h>
사용 네임스페이스 std;
int main()
{
정수 n, m;
벡터 < 벡터<정수 span>> > up1(n, 벡터 <int>(m));
정수 및 = 0;
for (int i = 1; i <= n; i++)
{
벡터 <정수> L(m + 1, 1< /span>), R(m + 1, m);
스택 <int>q;
for (int j = 1; j <= m; j++)
{
while (!q.empty() && up1 [i][j] < up1[i][q.top()])
{
R[q.top()] = j - 1;
q.팝();
}
qpush(j);
}
동안 (!q.empty())
q.팝();
for (int j = m; j >= 1; j--)
{
while (!q.empty() && up1 [i][j] < up1[i][q.top()])
{
L[q.top()] = j + 1;
q.팝();
}
qpush(j);
}
for (int j = 1; j <= m; j++)
ans = max(ans, up1[i][j] * (R[j] < span style="color:#666666">- L[j] + 1));
}
cout << ans;
반환 0;
}
1) O(n+m) 2) O(nm) 3) O(n^2*m) 4) 오(n*m^2)
Выберите правильный ответ, либо введите его в поле ввода
Комментарий учителя