分治算法寻找两个有序元素之间最大差值

Question

给定一个整数数组 arr[]，找出任意两个元素之间的差值，使得较大的元素在 arr[] 中的位置在较小的元素之后。

Max Difference = Max { arr[x] - arr[y] | x > y }

例子：

• 如果数组是[2, 3, 10, 6, 4, 8, 1, 7]，则返回值应该是8（10和2之间的差）。

• 如果数组是[7, 9, 5, 6, 3, 2]，则返回值应该是2（7和9之间的差）。

我的算法：

我想使用D&C算法。 解释

2, 3, 10, 6, 4, 8, 1, 7

then

2,3,10,6      and     4,8,1,7

then

2,3  and 10,6  and  4,8 and 1,7

then

2 and 3   10 and 6   4 and 8    1 and 7

由于这些元素将保持相同的顺序，因此我将获得最大差异，这里是6。

现在，我将回到合并这些数组，并再次找到第一个块的最小值和第二个块的最大值之间的差异，并一直重复此操作直到结束。

我无法在我的代码中实现这一点。是否有人可以为此提供伪代码？

- instance

---

请问您能否把问题表述得更清楚一些？看起来您似乎是想先实现归并排序，然后再做其他事情。 - Am_I_Helpful

@shekharsuman 我想要满足索引x > y的最大值(arr[x]-arr[y])。 - instance

Answer 1

我们有一个公式：max { A[i] - A[j] | i > j } = max { A[i] - min { A[j] | j < i } | i }，这个公式可以得出一个简单的O(n)算法：

我们只需要从左到右遍历数组A，记录当前最小值和最大差值即可。

prefix_min = A[0]
result = -infinity
for i := 1 to n - 1:
    # invariant: We have prefix_min = min { A[j] | j < i }
    result = max(result, A[i] - prefix_min)
    prefix_min = min(prefix_min, A[i])

分治算法在概念上更加复杂，但也能导致线性时间的解决方案（尽管常数因子较高）。

- Niklas B.

---

非常优雅的解决方案。 - Abhishek Bansal

你所提到的问题是一个分治算法，而你已经实现了Kadane算法。 - human.js

Answer 2

假设你想要找到最大差异 LD(A[])

完整的伪代码如下:

将数组分成两个部分A1[]和A2[]。

Find minimum & maximum element in A1[] and LD(A1).
Find minimum & maximum element in A2[] and LD(A2).

LD(A) = max( LD(A1), LD(A2), MAX(A2) - MIN(A1) )
MAX(A) = max( MAX(A1), MAX(A2) )
MIN(A) = min( MIN(A1), MIN(A2) )

基本情况（length(A) == 2）：

If A[1] > A[0], 
  LD(A) = A[1] - A[0].
  MAX(A) = A[1]
  MIN(A) = A[0]
else
  LD(A) = 0.
  MAX(A) = A[0]
  MIN(A) = A[1]

注意：

If (length(A) == 1)
    LD(A) = 0
    MIN(A) = MAX(A) = A[0]

同样地，您可以计算每个子数组中的最小和最大元素。

- Abhishek Bansal

---

你认为他问了同样的问题吗？实际上，这是他想要实现的算法！你的回答并没有解决他的问题！请再次仔细阅读他的示例。 - Am_I_Helpful

@shekharsuman 他需要他的算法的伪代码。我已经为他提供了。 - Abhishek Bansal

@AbhishekBansal，你能提供一个线性时间的解决方案吗？目前它的运行时间是O(nlogn)。 - rombi

Answer 3

以下是使用分治法的C代码。
请随意评论。

#include <stdio.h>

struct data{
    int min_;
    int max_;
};

struct data crossminmax(int *p,int lo,int mid,int hi){
    int i,min,max;
    struct data temp;

    min = p[mid];
    for(i=mid;i>=lo;i--){
        if(p[i] < min){
            min = p[i];
        }
    }

    max = p[mid+1];
    for(i=mid+1;i<=hi;i++){
        if(p[i] > max){
            max = p[i];
        }
    }
    temp.min_ = min;
    temp.max_ = max;
    return temp;
}

/* MinMax calculates the difference between Biggest and Smallest element  *
 * of an array using divide and conquer principles such that the position * 
 * of Biggest element is always greater than the Samllest element         */

struct data minmax(int *p,int lo,int hi){
    int mid,leftdiff,rightdiff,crossdiff;
    struct data left,right,cross,temp;

    if(lo == hi){
        temp.min_ = p[lo];
        temp.max_ = p[hi];
        return temp;
    }

    mid = (lo+hi)/2;
    left = minmax(p,lo,mid);
    right = minmax(p,mid+1,hi);

    cross = crossminmax(p,lo,mid,hi);
    leftdiff = left.max_ - left.min_;
    rightdiff = right.max_ - right.min_;
    crossdiff = cross.max_ - cross.min_;

    if(leftdiff > rightdiff && leftdiff > crossdiff){
        return left;
    }else if(rightdiff > crossdiff){
        return right;
    }else{
        return cross;
    }
}

int main(){
    int arr[] = {5,2,3,10,1,3,16,4,3};
    struct data dt;
    dt = minmax(arr,0,8);
    printf("Max difference = %d, Max Element=%d, Min Element = %d  \n",dt.max_ - dt.min_,dt.max_,dt.min_);
    return 0;
}

- Mav55

---

欢迎来到Stack Overflow！虽然这可能回答了问题，但最好在此处包含答案的基本部分，并提供参考链接。 - Nathan Tuggy

感谢Nathan和chiwangc的建议。 - Mav55

Answer 4

数组中最大差值

condition : - larger number should appear after smaller number
{ 10, 3, 6, 4, 8, 1, 7 }     6
{ 2, 3, 10, 6, 4, 8, 1 }     8
{ 7, 9, 5, 6, 3, 2 }         1
{ 1, 2, 3, 4 }               3
{ 4, 3, 2, 1  }              0



#include<stdio.h>
int main(){
  int n = 7;
  int arr[7] = { 10, 3, 6, 14, 8, 1, 7 };

  int i;
  int max_diff = 0;
  int min = arr[0];

  for( i=0; i<n; i++){
    if( (arr[i] - min) > max_diff ){
      max_diff = arr[i] - min;
    }

    if(arr[i] < min){
      min = arr[i];
    }
  }
  printf("max diff = %d", max_diff);

  return 0;
}

//时间复杂度 O(n)

//空间复杂度 O(1)

为了更好的理解，请访问https://www.youtube.com/watch?v=thPG6eTPf68&t=130s

- sandeep bairwa