#include <algorithm> #include <iostream> #include <stack> using namespace std; int arr[50005]; int ap1[50005]; int ap2[50005]; stack<int> st; int main() { int t; cin >> t; int s = 1; while (t--) { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &arr[i]); } //[1--i],栈内元素为左边界,数组元素为右边界 int num = 0; for (int i = 1; i <= n; i++) { ap1[i] = ap1[i - 1];//在前面基础上计算前缀和 num = 0; while (!st.empty() && st.top() < arr[i])//要求右边界都要大于前面元素 { num++;//计算左边界个数 st.pop(); } if (!st.empty()) ap1[i] += num + 1; //此时右边界小于栈元素,此元素可以做为左边界 else ap1[i] += num; st.push(arr[i]);//入栈成为:左边界 } while (!st.empty()) st.pop(); //[i-n] 栈内元素为*右*边界,数组元素为左边界 for (int j = n; j > 0; j--) { ap2[j] = ap2[j + 1]; num = 0; while (!st.empty() && arr[j] > st.top())//要求左边界都要大于后面元素 { num++;//计算右边界 st.pop(); } if (!st.empty()) ap2[j] += num + 1;//此时左边界小于栈元素,此元素可以做为右边界 else ap2[j] += num; st.push(arr[j]);//入栈,成为右边界 } while (!st.empty()) st.pop(); int ans = -1, pos = 0; for (int i = 1; i <= n; i++) { if (ap1[n] - ap1[i] - ap2[i + 1] > ans) { ans = ap1[n] - ap1[i] - ap2[i + 1]; pos = i + 1; } ap1[i] = 0; ap2[i] = 0; } printf("Case #%d: %d %d\n", s, pos, ans); s++; } }
全部评论
(0) 回帖