c++ - 分而治之以找到数组中的最大差异

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)

编辑:这是上述算法的 C++ 实现

#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;
}

希望对您有所帮助!!!