0

我要解决的问题如下：我想在给定数组中找到最大数字跨度，给定一个由正整数和负整数组成的数组 A 返回最大的 (A[j] - A[i] ) 使得 1<= i < j <= n，我想出了以下 nlogn 时间算法来解决这个问题 - ：

  1. 找到数组的第 n 阶统计量的索引让它为“i”
  2. 找到数组的一阶统计量的索引让它为“j”
  3. 如果 i > j，则返回差值，因为我们找到了数组的最大和最小元素之间的差值，因此终止返回差值。
  4. 如果 j > i 然后将数组分成两半，并通过递归调用此算法找到两半中的最大跨度，即 A[1....i] 和 A[i + 1 ......n]，情况是当算法找到这样的一对 i,j 它返回这些对之间的差异，否则它会继续递归并最终终止。
  5. 返回最大值{子数组 1 的最大跨度，子数组 2 的最大跨度}

这个算法是 O(nlogn) 但我不知道它是否正确。

4

2 回答 2

3

@mrip 解决方案的复杂性是时间上的 O(n) 和空间上的 O(n)。这是正确的，但是对于这个问题，只有 O(1) 的空间复杂度就足够了。

int min=a[0],ans=0;
for (int i=1;i<n;i++)
    if (a[i]<min) min=a[i];
    else ans=max(ans,a[i]-min);
return ans;
于 2013-10-11T04:30:52.730 回答
2

这是一个 O(n) 算法。

  1. 构建一个数组 Max，其中 Max[i] 是 k>=i 时 A[k] 的最大值。这可以通过向后迭代 A 在 O(n) 时间内完成。
  2. 构建一个数组 Min，其中 Min[i] 是 k<=i 时 A[k] 的最小值。再次O（n）。
  3. 遍历 Max 和 Min 以找到最大化 Max[i]-Min[i] 的索引 i。也是 O(n)。
  4. 返回 (Min[i],Max[i])。

编辑时：有一个极端情况，其中数组是反向排序的，在这种情况下，所有 i 的 Max[i]=Min[i]=A[i]。这可以在 O(n) 时间内检测到，在这种情况下，您只需返回最大化 A[i+1]-A[i] 的一对相邻元素（这将是负数）。

于 2013-10-10T23:58:19.640 回答