分而治之，找到数组中的最大差异

Question

我想解决一个问题，给定一个数组我需要计算最大差异，以便较大的元素出现在较小的元素后面。

这里是一个更好的问题陈述：

考虑到股票价格上每一天n天，什么是最大利润的人可以正好做一个交易做。一笔交易意味着该人可以在一天内买入一只股票，并在稍后的日期卖出。

我想用分而治之的算法来解决这个问题。

在我的递归函数中，我试图将数组分成两半，但我不确定如何处理逻辑。我是否在每一半中获得最大差异并进行比较？

int calculateMaxDiff(int *src, int start, int end){ 
    if(end - start == 1) return src[start]; 

    int middle = (start + end)/ 2; 
    int half1_diff; 
    int half2_diff; 
    half1_diff = calculateMaxDiff(src, start, middle); 
    half2_diff = calculateMaxDiff(src, middle, end); 

    //Do i need to have two loops here that calculate the diffs for each halves 
    .... 
    return max(half1_diff, half2_diff); 
} 

编辑：实施例输出

举一个数组{12，9，18，3，7，11，6，15，6,1，10}应该返回12的结果15和3之间的差异

Answer 1

在你的问题的问题都可以转化为一个更好的问题陈述的例子：

由于股票价格的每一天对于n天，通过完成一次交易，一个人可以获得的最大利润是多少。一笔交易意味着该人可以在一天内买入一只股票，并在稍后的日期卖出。

分而治之的解决方案：让我们看看我们是否能够通过拆分输入了一半，每个子阵列解决这个问题，那么两者结合起来解决这个问题。事实证明，我们实际上可以做到这一点，并且可以高效地做到！直觉如下。如果我们有一天的时间，最好的选择是当天买入，然后在同一天卖出，无利可图。否则，将数组分成两半。如果我们考虑最佳答案可能是什么，它必须位于三个位置之一：

1. 正确的买入/卖出对在上半部分完全发生。
2. 正确的买入/卖出对在下半年完全发生。
3. 正确的买入/卖出对发生在两个半部分 - 我们在上半年买入，然后在下半年卖出。

我们可以通过在第一和第二半上递归地调用我们的算法来获得（1）和（2）的值。对于期权（3）而言，获得最高利润的方法是在上半年的最低点买入，并在下半年卖出最高点。通过对输入进行简单的线性扫描并找到两个值，我们可以在两半中找到最小值和最大值。然后这给了我们一个算法，下面的重现：

T(n) = 2T(n/2) + O(n) 

T(n) = O(nlogn) 

这是一个简单的Python实现。它非常简单易懂，它也很容易转换为C++：

def DivideAndConquerSingleSellProfit(arr): 
    # Base case: If the array has zero or one elements in it, the maximum 
    # profit is 0. 
    if len(arr) <= 1: 
     return 0; 

    # Cut the array into two roughly equal pieces. 
    left = arr[ : len(arr)/2] 
    right = arr[len(arr)/2 : ] 

    # Find the values for buying and selling purely in the left or purely in 
    # the right. 
    leftBest = DivideAndConquerSingleSellProfit(left) 
    rightBest = DivideAndConquerSingleSellProfit(right) 

    # Compute the best profit for buying in the left and selling in the right. 
    crossBest = max(right) - min(left) 

    # Return the best of the three 
    return max(leftBest, rightBest, crossBest) 

编辑：这里是上述算法

#include <iostream> 
#include <algorithm> 
using namespace std; 
int calculateMin(int a[], int low, int high) 
{ 
    int i,mini; 
    mini = a[low]; 
    for(i=low;i<=high;i++) 
    { 
     if(a[i]<mini) 
     { 
      mini = a[i]; 
     } 
    } 
    return mini; 
} 
int calculateMax(int a[], int low, int high) 
{ 
    int i,maxi; 
    maxi = a[low]; 
    for(i=low;i<=high;i++) 
    { 
     if(a[i]>maxi) 
     { 
      maxi = a[i]; 
     } 
    } 
    return maxi; 
} 
int calculateMaxDiff(int a[], int low, int high) 
{ 
    if(low>=high) 
     return 0; 

    int mid = (low+high)/2; 
    int leftPartition = calculateMaxDiff(a,low,mid); 
    int rightPartition = calculateMaxDiff(a,mid+1,high); 
    int left = calculateMin(a,low,mid); // calculate the min value in the left partition 
    int right = calculateMax(a,mid+1,high); // calculate the max value in the right partition 
    return max(max(leftPartition, rightPartition), (right - left)); 

} 
int main() { 
    int arr[] = {12, 9, 18, 3, 7, 11, 6, 15, 6, 1 ,10}; 
    int len = sizeof(arr)/sizeof(arr[0]); 
    int ans = calculateMaxDiff(arr, 0, len-1); 
    cout << "Maximum Profit: " <<ans<<endl; 
    return 0; 
} 

希望它可以帮助C++实现！

Answer 2

分而治之算法的关键是征服部分。

对于这个问题的最重要的条件是：

较小元件

对于数组src后较大的元素出现时，分割src至2的两半，half1和half2后，假设答案将在i和j的位置上，现在有3种情况：

1. i和j都在half1 - >half1_diff
2. i和j都在half2 - >half2_diff
3. i是half1和j是half2

所以主要部分是处理与case3。由于较大的一个来了，所以我们只需要找到half1中的最小值min_half1和half2中的最大值max_half2，并检查它是否满足条件max_half2 >= min_half1并更新结果为max(half1_diff, half2_diff, max_half2-min_half1)。

为了计算min_half1和max_half2有效，你必须保持的min记录和阵列的max价值，它需要O(1)时间。

所以T(n) = 2T(n/2) + O(1),T(n) = O(n)。

---

详细信息请参考

http://ideone.com/TbIL2r

Answer 3

有复杂d/C算法，因为与检查像

maxdiff = max(current - min_so_far, maxdiff) 
update min_so_far 

简单循环解决

如果你真的想应用分而治之的方法，你可以返回三重{local_min, local_max, local_max_diff}问题没有必要从递归功能如：

left = calculateMaxDiff(start, middle) 
right = calculateMaxDiff(middle + 1, end) 
return {min(left.local_min, right.local_min), 
     max(left.local_max, right.local_max), 
     max(left.local_diff, right.local_diff, right.localmax - left.local_min)