從數組中計數可行的子列表長度

Question

這是一個遺傳算法的適應度函數，所以重要的是我可以儘可能有效地做到這一點，因爲它會一遍又一遍地重複。假設有一個函數foo（int [] array），如果該數組是「好」數組，則返回true;如果該數組是「壞」數組，則返回false。什麼使它好或壞在這裏並不重要。這不是我們在這裏定義的功能。它僅僅依賴於我試圖弄清的功能。

給定完整的數組[1,6,8,9,5,11,45,16,9]，可以說子數組[1,6,8]是一個由foo定義的「好」數組）和[9,5,11,45]是由foo（）定義的「好」數組。此外[5,11,45,16,9]是一個「好」陣列，也是最長的「好」子陣列。注意雖然[9,5,11,45]是一個「好」數組，而[5,11,45,16,9]是一個「好」數組，[9,5,11,45,16,9] ]是一個「壞」數組。

注意它不是我們定義的foo（）函數。我們所關心的是，我們將全部數組的所有可能的子數組，發送給foo（），查找它們的好壞，並計算它們的長度。唯一的問題是我們不希望將「好」子陣列的「好」子陣列包括在內，但是有一些「好」的子陣列可能在另一個好的子陣列中開始，但在其之外結束。

我們想要所有「好」數組的長度計數，但不是「好」數組的子數組。此外，如上所述，一個「好」數組可能會在另一個「好」數組的中間開始，但這兩者的組合可能是「壞」數組。

Answer 1

您需要遞歸算法將其結果保存到某個外部數據結構中。

它應該以子數組的開始和結束索引作爲參數，檢查它是否好。

如果數組好，那麼它的start和end索引應該存儲在該外部結構中。否則，您應該進行2次遞歸調用：從start索引到end-1索引和從start+1索引到end索引。

public void getLargestGoodArrays (int start, int end) { 
    if (isGood (start, end) { 
     saveGoodArray (start, end); 
    } else { 
     //here you should iterate through all already found good arrays to check whether the array with larger bounds already saved 
     if (!isSubarrayOfGoodArray (start, end - 1)) { 
     getLargestGoodArrays (start, end - 1); 
     } 
     if (!isSubarrayOfGoodArray (start + 1, end)) { 
     getLargestGoodArrays (start + 1, end); 
     }   
    } 
}