一道算法题给出一个由n个数组成的数组n不超过510的五次方你需要创建一个新数组长度也为n且每一格上的数都小于等于原数组同一格子上的数新数组必须是先单调不减再单调不增的在符合条件的新数组里n个元素的和要尽量的大问这个和的最大值。样例输入：61 1 4 5 1 4样例输出：13

思路：先从左往右扫描一遍数组，保证新数组单调不减；再从右往左扫描一遍数组，保证新数组单调不增。这样得到的新数组必定是符合条件的，且和最大。具体实现时，可以使用两个单调栈，一个从左往右维护单调不减的子序列，另一个从右往左维护单调不增的子序列。时间复杂度为O(n)。

Python代码：

原文地址: https://www.cveoy.top/t/topic/d4Fy 著作权归作者所有。请勿转载和采集!