求不含首尾元素的所有子数组最大值之和的高效算法

核心思路 #

避开O(n²)枚举子数组的关键是：计算每个元素作为最大值时，能覆盖多少个符合条件的子数组，再将元素值乘以对应子数组数量，累加得到总和。这种方法可以通过单调栈实现O(n)时间复杂度，非常适合大规模数组场景。

具体步骤 #

我们只需要处理数组中排除首尾元素的中间部分（比如示例arr = [4,3,5,2,8,1]的有效区间是索引1到4的元素[3,5,2,8]）。对每个有效元素arr[i]：

1. 找到左边第一个比它大的元素的索引left[i]（不存在则为-1）
2. 找到右边第一个大于等于它的元素的索引right[i]（不存在则为数组长度n）
3. 计算以arr[i]为最大值的符合条件的子数组数量：
   • 左可选起始位置数：i - max(left[i], 有效区间左边界-1)（确保起始位置不小于有效左边界）
   • 右可选结束位置数：min(right[i], 有效区间右边界+1) - i（确保结束位置不大于有效右边界）
   • 当前元素贡献值：arr[i] * 左数 * 右数

单调栈实现细节 #

单调栈用于维护一个单调递减的索引序列，能在遍历过程中快速定位每个元素的左右边界：

• 计算左边界：从左到右遍历有效区间，弹出栈中所有小于等于当前元素的索引，栈顶即为左边界；
• 计算右边界：从右到左遍历有效区间，弹出栈中所有小于当前元素的索引，栈顶即为右边界；

代码实现（Python） #

def sum_subarray_max_without_ends(arr):
    n = len(arr)
    if n <= 2:
        return 0  # 无符合条件的子数组
    low, high = 1, n - 2
    
    # 计算左边界：左边第一个大于当前元素的索引
    left = [-1] * n
    stack = []
    for i in range(low, high + 1):
        while stack and arr[stack[-1]] <= arr[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    # 计算右边界：右边第一个大于等于当前元素的索引
    right = [n] * n
    stack = []
    for i in range(high, low - 1, -1):
        while stack and arr[stack[-1]] < arr[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    # 累加所有贡献
    total = 0
    for i in range(low, high + 1):
        left_cnt = i - max(left[i], low - 1)
        right_cnt = min(right[i], high + 1) - i
        total += arr[i] * left_cnt * right_cnt
    return total

# 测试示例
arr = [4, 3, 5, 2, 8, 1]
print(sum_subarray_max_without_ends(arr))  # 输出57

示例验证 #

对示例[4,3,5,2,8,1]，所有符合条件的子数组最大值之和计算如下：

• 元素3：贡献3*1=3（对应子数组[3]）
• 元素5：贡献5*4=20（对应子数组[3,5],[5],[5,2],[3,5,2]）
• 元素2：贡献2*1=2（对应子数组[2]）
• 元素8：贡献8*4=32（对应子数组[3,5,2,8],[5,2,8],[2,8],[8]）
  总和：3+20+2+32=57，与代码输出一致。

复杂度分析 #

• 时间复杂度：O(n)，每个元素入栈、出栈各一次，遍历计算贡献也是O(n)；
• 空间复杂度：O(n)，用于存储左右边界数组和单调栈。

内容的提问来源于stack exchange，提问作者user23753283