स्पर्शोन्मुख की गणना - 9
Задача
नीचे दिए गए कोड के लिए, एसिम्प्टोटिक्स खोजें:
<पूर्व शैली = "मार्जिन-बाएं: 0 पीएक्स; मार्जिन-दाएं: 0 पीएक्स">
#include <bits/stdc++.h>
उपयोग नाम स्थान एसटीडी;
int मुख्य()
{
int n, m;
वेक्टर < vector<int> > up1(n, वेक्टर <int>(m));
int ans = 0;
के लिए (int i = 1; i <= n; i++)
{
वेक्टर <int> एल(एम + 1, 1< /span>), R(m + 1, m);
स्टैक <int>क्यू;
के लिए (int j = 1; j <= m; j++)
{
जबकि (!q.empty() && up1 [i][j] < up1[i][q.top()])
{
R[q.top()] = j - 1;
क्यू पॉप ();
}
क्यूपुश (जे);
}
जबकि (!q.empty())
क्यू पॉप ();
के लिए (int j = m; j >= 1; j--)
{
जबकि (!q.empty() && up1 [i][j] < up1[i][q.top()])
{
L[q.top()] = j + 1;
क्यू पॉप ();
}
क्यूपुश (जे);
}
के लिए (int j = 1; j <= m; j++)
उत्तर = max(ans, up1[i][j] * (आर[जे] < स्पैन स्टाइल="रंग:#666666">- एल[जे] + 1));
}
cout << ans;
वापसी 0;
}
1) ओ(एन+एम) 2) ओ (एनएम) 3) ओ(एन^2*एम) 4) ओ(एन*एम^2)
Выберите правильный ответ, либо введите его в поле ввода
Комментарий учителя