蓝桥杯 最大区间

原题目链接

问题描述

给定一个长度为n的序列A_i，求一对L, R使得：

(R - L + 1) * min(A_L, A_{L+1}, ..., A_R)

的值尽可能大，其中min表示该区间中的最小值。

你只需要输出该表达式的最大值，无需输出具体的L和R。

输入格式

• 第一行包含一个整数n，表示序列的长度。
• 第二行包含n个整数，分别表示A_1, A_2, ..., A_n，相邻两个整数之间使用一个空格分隔。

输出格式

输出一行，包含一个整数，表示答案。

样例输入

5 1 1 3 3 1

样例输出

6

评测用例规模与约定

• 对于 40% 的评测用例：1 ≤ n ≤ 5000，1 ≤ A_i ≤ 5000
• 对于所有评测用例：1 ≤ n ≤ 3×10^5，1 ≤ A_i ≤ 10^9

c++代码

#include<bits/stdc++.h>#include<stdio.h>usingnamespacestd;typedeflonglongll;ll n,ans=0;vector<ll>arr,nextsmall,lastsmall;intmain(){stack<ll>st,sk;scanf("%lld",&n);arr=vector<ll>(n),nextsmall=vector<ll>(n,n),lastsmall=vector<ll>(n,-1);for(ll i=0;i<n;i++){scanf("%d",&arr[i]);}for(ll i=0;i<n;i++){while(!st.empty()&&arr[i]<arr[st.top()]){nextsmall[st.top()]=i;st.pop();}st.push(i);}for(ll i=n-1;i>=0;i--){while(!sk.empty()&&arr[i]<arr[sk.top()]){lastsmall[sk.top()]=i;sk.pop();}sk.push(i);}for(ll i=0;i<n;i++){ll left=lastsmall[i]+1,right=nextsmall[i]-1;ans=max(ans,(right-left+1)*arr[i]);}printf("%lld",ans);return0;}//by wqs

算法讲解

用单调栈

这道题目，先选取一个值假设这个值就是最小的，然后不断向两边扩散，使得R - L最大，前提是保证这个值最小。

如何快速得到L和R，就是快速得到右边第一个比他大的，和左边第一个比他小的，这就是经典的单调栈问题。