分而治之，找到數組中的最大差異

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)