algorithm - 从给定数组的所有子区间中找出可能的最大差之和

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)有关，你可以看到here , 只是为了将来的问题知道它。

我会用伪代码来写。

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 函数只是读取堆栈中的下一个值而不弹出它。