一道算法题给出一个由n个数组成的数组n不超过510的五次方你需要创建一个新数组长度也为n且每一格上的数都小于等于原数组同一格子上的数新数组必须是先单调不减再单调不增的在符合条件的新数组里n个元素的和要尽量的大问这个和的最大值。时间复杂度为n方的话会超时样例输入：61 1 4 5 1 4样例输出：13
思路：先从左往右扫一遍，得到一个单调不减的数组a，再从右往左扫一遍，得到一个单调不增的数组b，然后对于每个位置i，取a[i]和b[i]中的较小值，即可得到符合条件的新数组。最后再计算新数组的元素和即可。
时间复杂度：O(n)
代码：
原文地址: https://www.cveoy.top/t/topic/d45c 著作权归作者所有。请勿转载和采集!