分而治之以找出阵列中的最大差异 [英] Divide and Conquer to find maximum difference in an array
问题描述
我正在尝试解决一个问题，在给定数组的情况下，我需要计算最大差异，以使较大的元素出现在较小的元素之后。
这是一个更好的问题陈述：
给出股票每天 n 天的价格，一个人仅完成一项交易即可获得的最大利润是多少。一笔交易意味着该人可以在一天之内买入一只股票，然后在以后的某个日期出售。
我正在尝试使用除法解决此问题并征服算法。
在递归函数中，我试图将数组分成两半，但我不确定如何进行逻辑处理。我只是得到每个半部分的最大差值并进行比较吗？
int computeMaxDiff（int * src，int start，int end） {
if（end-start == 1）return src [start];
int中间=（开始+结束）/ 2;
int half1_diff;
int half2_diff;
half1_diff = computeMaxDiff（src，start，middle）;
half2_diff = computeMaxDiff（src，middle，end）;
//我是否需要在这里有两个循环来计算每个一半的差异
...。
return max（half1_diff，half2_diff）;
}
编辑：示例输出
给定一个数组{12，9，18，3，7，11，11，6，15，6，1，，10}由于15和3之间的差而应返回12
问题中的问题可以转换为更好的问题陈述：
<假设n天每天的股票价格，一个人通过一次交易就能获得的最大利润是多少。一笔交易意味着该人一天可以买入一只股票，然后在以后的某个日期出售。
分而治之解决方案：让我们看看是否可以通过将输入分成两半，解决每个子数组中的问题，然后将两者组合在一起来解决此问题。事实证明，我们实际上可以做到这一点，并且可以做到高效！直觉如下。如果我们只有一天，那么最好的选择是在当天买入，然后在同一天将其卖回以赚取利润。否则，将阵列分成两半。如果我们考虑最佳答案是什么，它必须位于以下三个位置之一：
- 正确的买/卖对完全出现
- 正确的买/卖对完全在下半年出现。
- 正确的买/卖对出现在两个半部中-我们在上半年购买，然后在下半年出售。
我们可以获得（1）和（2 ）通过在前一半和后一半递归调用我们的算法。对于选项（3），获得最高利润的方法是在上半年的最低点买入，在下半年的最高点卖出。通过对输入进行简单的线性扫描并找到两个值，我们可以找到两个一半的最小值和最大值。然后，这为我们提供了具有以下重复性的算法：
T（n）= 2T（n / 2）+ O（n ）
T（n）= O（nlogn）
在Python中的简单实现。它非常容易理解，也很容易转换为C ++：
def DivideAndConquerSingleSellProfit（arr）：
＃Base情况：如果数组中有零个或一个元素，则
＃的最大利润为0。如果len（arr）<= 1：
则返回0；否则为
。
＃将数组切成两等份。
左= arr [：len（arr）/ 2]
右= arr [len（arr）/ 2：]
＃查找纯粹用于在左侧或纯在
＃右侧。
leftBest = DivideAndConquerSingleSellProfit（左）
rightBest = DivideAndConquerSingleSellProfit（右）
＃计算在左侧购买并在右侧出售的最佳利润。
crossBest = max（right）-min（left）
＃返回三个
中的最佳值return max（leftBest，rightBest，crossBest）
编辑：这是上述算法的C ++实现
#include< iostream>
#include< algorithm>
使用命名空间std;
int computeMin（int a []，int low，int high）
{
int i，mini;
mini = a [low];
for（i = low; i< high; i ++）
{
if（a [i]
mini = a [i ];
}
}
迷你回报；
}
int computeMax（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 computeMaxDiff（int a []，int low，int high）
{
if（low> = high）
return 0;
int中=（（低+高）/ 2）;
int leftPartition = calculateMaxDiff（a，low，mid）;
int rightPartition = CalculationMaxDiff（a，mid + 1，high）;
int剩余= calculateMin（a，low，mid）; //计算左分区中的最小值
int right = calculateMax（a，mid + 1，high）; //计算右分区
中的最大值return max（max（leftPartition，rightPartition），（right-left））;
}
int main（）{
int arr [] = {12，9，18，3，7，11，11，6，15，6，1，10} ;
int len = sizeof（arr）/ sizeof（arr [0]）;
int ans = calculateMaxDiff（arr，0，len-1）;
cout<< 最大利润：<< ans<< endl;
返回0；
}
希望有帮助！
I am trying to solve a problem where given an array I need to calculate the maximum difference such that the larger element appears after the smaller element.
Here is a better problem statement:
Given the stock prices on each day for n days, what is the maximum profit a person can make by doing exactly one transaction. One transaction means that the person can buy exactly one stock on one day and sell it on a later date.
I am trying to solve this problem using divide and conquer algo.
In my recursive function i am trying to spilt the array into two halves, but i am not sure on how to proceed with logic. Do i just get the max difference in each halves and compare?
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);
}
Edit: Example output
Give an array {12, 9, 18, 3, 7, 11, 6, 15, 6, 1 ,10} should return 12 as a result of difference between 15 and 3
The question in your problem can be translated into a better problem statement:
Given the stock prices on each day for n days, what is the maximum profit a person can make by doing exactly one transaction. One transaction means that the person can buy exactly one stock on one day and sell it on a later date.
The divide-and-conquer solution: Let's see if we can solve this by splitting the input in half, solving the problem in each subarray, then combining the two together. Turns out we actually can do this, and can do so efficiently! The intuition is as follows. If we have a single day, the best option is to buy on that day and then sell it back on the same day for no profit. Otherwise, split the array into two halves. If we think about what the optimal answer might be, it must be in one of three places:
- The correct buy/sell pair occurs completely within the first half.
- The correct buy/sell pair occurs completely within the second half.
- The correct buy/sell pair occurs across both halves - we buy in the first half, then sell in the second half.
We can get the values for (1) and (2) by recursively invoking our algorithm on the first and second halves. For option (3), the way to make the highest profit would be to buy at the lowest point in the first half and sell in the greatest point in the second half. We can find the minimum and maximum values in the two halves by just doing a simple linear scan over the input and finding the two values. This then gives us an algorithm with the following recurrence:
T(n) = 2T(n/2) + O(n)
T(n) = O(nlogn)
Here is a simple implementation in Python. Its very simple to understand and its also easy to convert to 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)
Edit: Here is the C++ implementation for the above algorithm
#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;
}
Hope it helps!!!
这篇关于分而治之以找出阵列中的最大差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
