Для приведенного ниже кода, найдите асимптотику:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
vector < vector<int> > up1(n, vector <int>(m));
int ans = 0;
for (int i = 1; i <= n; i++)
{
vector <int> L(m + 1, 1), R(m + 1, m);
stack <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.pop();
}
q.push(j);
}
while (!q.empty())
q.pop();
for (int j = m; j >= 1; j--)
{
while (!q.empty() && up1[i][j] < up1[i][q.top()])
{
L[q.top()] = j + 1;
q.pop();
}
q.push(j);
}
for (int j = 1; j <= m; j++)
ans = max(ans, up1[i][j] * (R[j] - L[j] + 1));
}
cout << ans;
return 0;
}
1) O(n + m) 2) O(nm) 3) O(n^2*m) 4) O(n*m^2)