一个数组，对于某个区间，这个区间的和*这个区间中的最小值=这个区间的计算值。求这个数组中的最大计算值，并任意输出其的一个左右位置。
思路：
维护一个最小单调栈。
对于某个元素：
如果被弹出了，说明它最多向右延伸到这里。
对于进栈，如果它的进栈没有造成任何元素的弹出，则说明它的位置就是它左边能延伸到的位置。如果造成元素弹出，那么，最后一个弹出的元素的左边能延伸到的位置就是本元素往左能延伸到的位置。
对于两个元素相同时：我不作弹出处理，仅仅把这个元素的位置更新（代码中表现为把这个元素往左延伸的和更新）。
在弹出元素时，能求和，而这个和正是元素往右延伸的和。往左延伸的和已经算好，所以这个元素为最小值的最大区间值就可以知道了。
Read full article from POJ 2796: Feel Good - ShineCheng - 博客园
No comments:
Post a Comment