求给定数组的所有子区间可能的最大差值之和

Question

我在设计算法时遇到问题。问题是这应该在 O(n( 时间内执行。

这是作业：有一个带有 n 个数字的未排序数组 "a"。

mij=min{ai, ai+1, ..., aj}, Mij=max{ai, ai+1, ..., aj}

算：

S=SUM[i=1,n] { SUM[j=i,n] { (Mij - mij) } }

我能够在O(nlogn(时间内解决这个问题。这是一项大学研究任务。我尝试的一切都表明这是不可能的。如果您能为我指出找到解决方案的正确方向，我将不胜感激。或者至少证明这是不可能的。

---

进一步解释：

给定 i 和 j ，求数组切片 a[i：j] 的最大和最小元素。 减去这些以获得切片的范围，a[max]-a[min] 。

现在，将所有切片的范围相加 (i， j( 以便1 <= i <= j <= n . 在O(n(时间内完成。

Answer 1

这是一个非常简单的问题。我假设它是对象数组(如值对或元组(而不是数字。第一个值是数组中的索引，第二个值是值。

这里正确的问题是我们需要多少时间将每个数字相乘并从总和中加/减它，即它是最大和最小元素的子序列数。这个问题与寻找下一个最大元素(nge(有关，你可以在这里看到，只是为了了解它以备将来的问题。

我将用伪代码编写它。

subsum (A):
    returnSum = 0
    //i am pushing object into the stack. Firt value is index in array, secong is value
    lastStackObject.push(-1, Integer.MAX_INT)
    for (int i=1; i<n; i++)
        next = stack.pop()
        stack.push(next)
        while (next.value < A[i].value)
            last = stack.pop()
            beforeLast = stack.peek()
            retrunSum = returnSum + last.value*(i-last.index)*(last.index-beforeLast.index)
        stack.push(A[i])
    while stack is not empty:
        last = stack.pop()
        beforeLast = stack.peek()
        retrunSum = returnSum + last.value*(A.length-last.index)*(last.index-beforeLast.index)
    return returnSum
sum(A)
    //first we calculate sum of maximum values in subarray, and then sum of minimum values. This is done by simply multiply each value in array by -1
    retrun subsum(A)+subsum(-1 for x in A.value)

此代码的时间复杂度为 O(n(。

Peek功能只是在不弹出的情况下读取堆栈中的下一个值。