UVA1619 感觉不错 Feel Good（良好的感觉） 题解

0.题面：

给出正整数n和一个(1 <= n <= 100 000)长度的数列，要求找出一个子区间，使这个子区间的数字和乘上子区间中的最小值最大。输出这个最大值与区间的两个端点。 1.思路 一开始试图使用单调栈，然而在调试一上午无果后愤然打了个分治，然后就过了233 根据分治三步法，算法流程分为： 1.分解：定义 /(dfs(l,r)/) 为区间 /([l,r]/) 的最优解，/(mid = (l+r)/2/) ，可以把问题分为 /(dfs(l,mid)/) 和 /(dfs(mid+1,r)/) 两部分，分别对应最优解完全位于左子区间和右子区间的情况。 2.边界：当 /(l=r/) 时，/(dfs(l,r)={a_l}^2/)。(数列为/(a/)) 3.合并：在第一步处理了最优解完全位于左子区间和右子区间的情况，还有最优解跨越 /(mid/) 的情况没处理。注意到当最小值一定时，区间越大越好，所以可以从大到小地选择最大值，再从中点开始往左右两端“放宽”当前区间。 2.Code #inclu

UVA1619 感觉不错 Feel Good（良好的感觉） 题解最先出现在Python成神之路。