P2659 美丽的序列 题解

## [P2659 美丽的序列](https://www.luogu.com.cn/problem/P2659) ## 题目大意： 给出一个序列，找出一个子区间，使该区间的最小值与区间长度乘积最大。 ## solution: 我们可以枚举最小值：对于每一个数列中的数字 $a_i$ ，找到当它作为数列最小值时最长的序列，分别用数组 $zuo[i]$ 与 $you[i]$ 保存这时 的左右端点。 以上操作我们可以用单调栈实现，正序找第一个比 $a[ $ $ i $ $ ]$ 小的位置 $-1$ 后就是右端点，栈里还有找不到比它小的数，把 $you[$ $i$ $ ] $ 赋成 $n$ ,倒序 $+1$ 后就是左端点,剩余 $zuo[ $ $ i $ $ ]$ 赋成 $1$ 。 最后 $\max \limits_{i=1}^{n} (you[i]-zuo[i]+1)\times a[i]$ 。 ## 接下来是细节的处理： 乘积可能大于 $\text{int}$ 的范围，要开 $\text{long long }$ 。 看到这的同学，可以自己去写代码了(~~tf口吻~~) [code](https://www.luogu.com.cn/paste/354q5rqe) ### End ## 作者的碎碎念： 有用留赞(~~言简意赅~~)