遞歸，分而治之算法，用於最長的非減少數字數組

我對這個問題有一些嚴重的問題。我需要一個「分而治之」的遞歸算法，告訴我最長的非遞減數組數組的長度。就個人而言，我會選擇使用我在仔細閱讀問題之前編寫的代碼。遞歸，分而治之算法，用於最長的非減少數字數組

int bestIndex = 0; 
    int bestLength = 0; 
    int curIndex = 0; 
    int curLength = 1; 

    for (int i = 1; i < a.length; i ++){ 
     if (a[i] >= a[i-1]){ 
      curLength ++; 
     }else { 
      curLength = 1; 
      curIndex = i; 
     } 
     if (curLength > bestLength){ 
      bestIndex = curIndex; 
      bestLength = curLength; 
     } 
    } 
    return bestLength;

的問題是分配要求我使用分而治之，我想不出這樣做的方法。

一個例子是「4 2 3 3 1 2 4 5 9 2」這將返回「5」，因爲「1 2 4 5 9」

任何幫助不勝感激。

謝謝

來源

2011-10-11 John Smith

遍歷列表，並選擇「分割點」，以發生減少的地方。然而，除非你在中間選擇一個分割點，否則這不會真正「分裂」。我會從中間開始，然後向外迭代。以i = m（中）然後m-1，m + 1，m-2，m + 2等循環，直到i和i + 1之間的減小。然後將陣列切成兩半，然後在每一半上進行遞歸。如果不存在減少，則返回序列的長度。 – VoidStar

你確定子陣列需要由連續的元素組成嗎？這個問題得到了子序列的方式更有趣......

無論如何，如果你需要一分而治之算法儘量遵循的基本藍圖：

function f(array) = 
    if array is empty or constant size or something like that 
     handle base case 
    else 
     result1 <- f(first half of the array) 
     result2 <- f(second half of the array) 
     return some_way_to_combine(result1, result2)

當然，你需要正確選擇什麼˚F應回來幫助你。您將需要處理增加的子陣列位於其中一個半邊的情況以及跨越邊界的情況。

來源

2011-10-11 00:30:18 hugomg

其他答案是一個很好的通用答案。

但是，我將建議關鍵是要知道在結果結合時需要回答哪些問題。如果結果1代表陣列[I，J]和結果2代表[J + 1，K]那麼這些都是你需要能夠回答的問題：

什麼是最長的非遞減序列兩端在j？
什麼是從j + 1開始的最長非遞減序列？
到目前爲止，我所看到的最大長度序列是什麼（包括以j結尾並從j + 1開始的序列）？

如果你認爲你已經可以回答這些問題對RESULT1和RESULT2，那麼你應該能夠確定答案爲合併後的結果[I，K]（即最長始於我，和最長的序列開始於k，以及迄今爲止您所見過的最長的那兩個）。

來源

2011-11-10 23:50:15 Nate

遞歸，分而治之算法，用於最長的非減少數字數組

回答

相關問題