0

如何查找/存储长度为 n 的数组的所有可能的非空子数组的最大值/最小值？

如果确实查询到段树，我生成了数组的段树和每个可能的子数组，但这效率不高。我如何在 O(n) 中做到这一点？

PS n <= 10 ^7

For eg. arr[]= { 1, 2, 3 };  // the array need not to be sorted

sub-array     min      max
{1}            1        1
{2}            2        2
{3}            3        3
{1,2}          1        2
{2,3}          2        3
{1,2,3}        1        3
4

5 回答 5

2

我认为不可能将所有这些值存储在 O(n) 中。但是很容易在 O(n) 中创建一个可以回答的结构，在 O(1) 中查询“有多少子集，其中 A[i] 是最大元素”。

天真的版本：

想想简单的策略：要知道某个 A[i] 有多少这样的子集，您可以使用一个简单的 O(n) 算法来计算数组左侧和右侧有多少元素小于一个[我]。比方说：

A = [... 10 1 1 1 5 1 1 10 ...]

这个5向上的左边有 3 个元素，右边有 2 个元素。由此我们知道有一些4*3=12子数组5的最大值是最大值。因为左边和右边4*3都有子数组。0..30..2

优化版：

这种简单的检查版本将对每个元素进行 O(n) 次操作，所以毕竟 O(n^2)。如果我们可以一次通过 O(n) 计算所有这些长度不是很好吗？

幸运的是，有一个简单的算法。只需使用堆栈。正常遍历数组（从左到右）。将每个元素索引放入堆栈。但是在放之前，把所有值小于当前值的索引都去掉。当前索引之前的剩余索引是最近的较大元素。

要在右侧找到相同的值，只需向后遍历数组。

这是一个示例 Python 概念验证，它显示了该算法的实际应用。我还实现了 naïve 版本，因此我们可以交叉检查优化版本的结果：

from random import choice
from collections import defaultdict, deque

def make_bounds(A, fallback, arange, op):
    stack = deque()
    bound = [fallback] * len(A)
    for i in arange:
        while stack and op(A[stack[-1]], A[i]):
            stack.pop()
        if stack:
            bound[i] = stack[-1]
        stack.append(i)
    return bound

def optimized_version(A):
    T = zip(make_bounds(A, -1, xrange(len(A)), lambda x, y: x<=y), 
            make_bounds(A, len(A), reversed(xrange(len(A))), lambda x, y: x<y))

    answer = defaultdict(lambda: 0)
    for i, x in enumerate(A):
        left, right = T[i]
        answer[x] += (i-left) * (right-i)
    return dict(answer)

def naive_version(A):
    answer = defaultdict(lambda: 0)
    for i, x in enumerate(A):
        left = next((j for j in range(i-1, -1, -1) if A[j]>A[i]), -1)
        right = next((j for j in range(i+1, len(A)) if A[j]>=A[i]), len(A))
        answer[x] += (i-left) * (right-i)
    return dict(answer)


A = [choice(xrange(32)) for i in xrange(8)]    
MA1 = naive_version(A)
MA2 = optimized_version(A)

print 'Array:    ', A
print 'Naive:    ', MA1
print 'Optimized:', MA2
print 'OK:       ', MA1 == MA2
于 2015-08-13T05:51:38.683 回答
1

我认为不可能直接在 O(n) 时间内完成：您需要遍历子数组的所有元素，并且您有 n 个。除非子数组已排序。

另一方面，您可以在初始化子数组时，而不是使它们成为普通数组，而是可以构建堆，特别是当您想要找到最小堆时的最小堆和想要找到最大值时的最大堆。

构建堆是一个线性时间操作，并且分别为最大堆和最小堆检索最大值和最小值是一个恒定时间操作，因为这些元素是在堆的第一个位置找到的。

只需使用普通数组即可轻松实现堆。

查看维基百科上关于二进制堆的这篇文章：https ://en.wikipedia.org/wiki/Binary_heap 。

于 2015-08-13T02:08:53.277 回答
0

假设您的意思是连续子数组，请创建部分和数组，其中 Yi = SUM(i=0..i)Xi，因此从 1,4,2,3 创建 0,1,1+4=5,1+ 4+2=7,1+4+2+3=10。您可以在线性时间内从左到右创建它，并且任何连续子数组的值都是从另一个子数组中减去一个部分和，因此 4+2+3 = 1+4+2+3 - 1= 9。

然后从左到右扫描部分和，跟踪到目前为止看到的最小值（包括初始零）。在每个点从当前值中减去这个值，并跟踪以这种方式产生的最高值。这应该为您提供总和最大的连续子数组的值，并且您也可以保留索引信息，以查找该子数组的开始和结束位置。

要找到最小值，或者稍微改变上面的内容，或者只是颠倒所有数字的符号并再次做同样的事情：min(a, b) = -max(-a, -b)

于 2015-08-13T04:36:38.927 回答
0

我不明白您所说的最大子数组到底是什么意思，所以我假设您要求以下之一

  1. 最大/最小长度的子数组或其他一些标准（在这种情况下，问题将减少为在一维数组中查找最大元素）
  2. 在一个子数组的上下文中或在整个超级数组的上下文中，所有子数组的最大元素

问题 1 可以通过简单地迭代您的超级数组并存储对最大元素的引用来解决。或者像nbro所说的那样建立一个堆。问题 2 也有类似的解决方案。然而，线性扫描是通过n长度数组而m不是线性的。因此，您必须保持类不变量，以便在每次操作后知道最大值/最小值。也许在一些数据结构（如堆）的帮助下。

于 2015-08-13T02:23:32.413 回答
-1

我认为您要问的问题是找到子数组的最大值。bleow 是可以在 O(n) 时间内完成的代码。

int maxSumSubArr(vector<int> a)
{
    int maxsum = *max_element(a.begin(), a.end());
    if(maxsum < 0) return maxsum;
    int sum = 0;
    for(int i = 0; i< a.size; i++)
    {
      sum += a[i];
      if(sum > maxsum)maxsum = sum;
      if(sum < 0) sum = 0;
    }
    return maxsum;
}

注意：此代码未经测试，如果发现一些问题请添加评论。

于 2015-08-13T07:02:13.497 回答