所有子数组的最大元素之和，不包括第一个和最后一个元素

Question

我正在尝试制定一种算法来计算子数组中每个最大元素的总和，不包括第一个和最后一个元素。这种幼稚的方法是显而易见的，但我不希望这样。

如果目前还不清楚，这里有一个例子：

total = 0
arr = [4, 3, 5, 2, 8, 1]

我们从元素 4 和 5 开始，3 是唯一的数字，因此它是最大值，因此到目前为止的总数是 3。然后我们取 4 和 2，它们之间的最大值是 5，所以我们将其添加到总数中。我们取 4 和 8 和 5 仍然是最大值，所以我们当前的总数现在是 13。取 4 和 1，我们的最大元素为 8，所以我们将 8 添加到总数中，现在是 21。移动到 3 和 2（因为有没有介于 3 和 5 之间的元素）最大值为 5，因此我们将 5 添加到总数中。本质上，我们将继续在每个可能的子数组之间添加最大元素。我怎样才能有效地做到这一点？

我已经尝试过 O(n^2) 方法，显然效率很低，我想知道解决这个问题的更好方法。也许通过堆栈或指针？我不太确定。我正在尝试学习 DSA，作为我大学即将开设的 DSA 课程的预习

Answer 1

对于每个元素，我们可以计算包含它的最大子数组，其中它是最大元素（同时不与先前元素的子数组重叠，这可能发生在相邻相等元素的情况下）。有了这些信息，就可以通过将每个元素乘以它在其中出现的最大值的子数组数量来计算答案。这可以使用单调堆栈通过两次迭代在 O(n) 内完成。

C++ 示例实现：

#include <span>
#include <vector>
int solve(std::span<int> nums) {
    std::vector<int> leftLarger, stk;
    leftLarger.reserve(nums.size());
    stk.reserve(nums.size());
    for (int i = 0; i < ssize(nums); ++i) {
        while (!stk.empty() && nums[stk.back()] < nums[i]) stk.pop_back();
        leftLarger.push_back(stk.empty() ? 0 : stk.back());
        stk.push_back(i);
    }
    stk.clear();
    int ans = 0;
    for (int i = ssize(nums) - 1; ~i; --i) {
        while (!stk.empty() && nums[stk.back()] <= nums[i]) stk.pop_back();
        ans += nums[i] * ((stk.empty() ? ssize(nums) - 1 : stk.back()) - i) 
                       * (i - leftLarger[i]);
        stk.push_back(i);
    }
    return ans;
}