算法题：最大单调不减不增子序列和

算法题：最大单调不减不增子序列和

问题描述：

给出一个由 n 个数组成的数组，n 不超过 5*10^5，你需要创建一个新数组，长度也为 n，且每一格上的数都小于等于原数组同一格子上的数，新数组必须是先单调不减，再单调不增的，在符合条件的新数组里，n 个元素的和要尽量的大，问这个和的最大值。

样例输入：

6
1 1 4 5 1 4

样例输出：

13

思路：

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

Python 代码：

def max_sum_subsequence(nums):
    n = len(nums)
    increasing_stack = []  # 单调不减栈
    decreasing_stack = []  # 单调不增栈
    result = [0] * n

    # 从左往右扫描，维护单调不减子序列
    for i in range(n):
        if not increasing_stack or nums[i] >= increasing_stack[-1]:
            increasing_stack.append(nums[i])
        else:
            j = len(increasing_stack) - 1
            while j >= 0 and nums[i] < increasing_stack[j]:
                j -= 1
            increasing_stack[j + 1] = nums[i]

    # 从右往左扫描，维护单调不增子序列
    for i in range(n - 1, -1, -1):
        if not decreasing_stack or nums[i] <= decreasing_stack[-1]:
            decreasing_stack.append(nums[i])
        else:
            j = len(decreasing_stack) - 1
            while j >= 0 and nums[i] > decreasing_stack[j]:
                j -= 1
            decreasing_stack[j + 1] = nums[i]

    # 合并两个栈，得到最终结果
    i = 0
    j = 0
    k = 0
    while i < len(increasing_stack) and j < len(decreasing_stack):
        if increasing_stack[i] <= decreasing_stack[j]:
            result[k] = increasing_stack[i]
            i += 1
        else:
            result[k] = decreasing_stack[j]
            j += 1
        k += 1

    # 处理剩余元素
    while i < len(increasing_stack):
        result[k] = increasing_stack[i]
        i += 1
        k += 1
    while j < len(decreasing_stack):
        result[k] = decreasing_stack[j]
        j += 1
        k += 1

    return sum(result)

nums = [1, 1, 4, 5, 1, 4]
max_sum = max_sum_subsequence(nums)
print(max_sum)  # 输出 13