最高金額遞增子，改變算法使用記憶化

我有以下的代碼實現，而不是使用引用變量「X」來存儲整體最大這個問題的遞歸解決方案，如何我還是我可以返回結果從遞歸，所以我不必使用'x'這將有助於memoization？最高金額遞增子，改變算法使用記憶化

// Test Cases: 
// Input: {1, 101, 2, 3, 100, 4, 5} Output: 106 
// Input: {3, 4, 5, 10} Output: 22 

int sum(vector<int> seq) 
{ 
    int x = INT32_MIN; 
    helper(seq, seq.size(), x); 
    return x; 
} 

int helper(vector<int>& seq, int n, int& x) 
{ 
    if (n == 1) return seq[0]; 

    int maxTillNow = seq[0]; 
    int res = INT32_MIN; 

    for (int i = 1; i < n; ++i) 
    { 
     res = helper(seq, i, x); 
     if (seq[i - 1] < seq[n - 1] && res + seq[n - 1] > maxTillNow) maxTillNow = res + seq[n - 1]; 
    } 

    x = max(x, maxTillNow); 
    return maxTillNow; 
}

來源

2017-07-01 Samer Tufail

首先，我不認爲這個實現是正確的。對於此輸入{5, 1, 2, 3, 4}它給出14，而正確的結果是10.

對於爲此問題編寫遞歸解決方案，您不需要傳遞x作爲參數，因爲x是您期望從功能本身。相反，您可以構建如下的狀態：

當前索引：這是您在當前步驟中處理的索引。
最後採取數：這是你在你的結果序列包括到目前爲止的最後一個數字的值。這是爲了確保在以下步驟中選擇更大的數字以保持結果子序列的增加。

因此，您的函數定義類似於sum(current_index, last_taken_number) = the maximum increasing sum from current_index until the end, given that you have to pick elements greater than last_taken_number to keep it an increasing subsequence，其中您希望的答案是sum(0, a small value)，因爲它計算整個序列的結果。通過a small value我的意思是小於整個序列中的任何其他值。

sum(current_index, last_taken_number)可以遞歸使用更小的子狀態來計算。首先假設簡單情況：

N = 0，結果爲0，因爲您根本沒有序列。
N = 1，序列只包含一個數，其結果是要麼數或0的情況下，數是負的（我考慮空子序列作爲一個有效的子序列，因此不採取任何數量的是一個有效的答案）。

我們棘手的部分，當N> = 2

假設N = 2。在這種情況下，有兩個選項：

中忽略所述第一數目，則該問題可以被簡化爲N = 1版本，其中該編號是序列中的最後一個。在這種情況下，結果是一樣的sum(1,MIN_VAL)，其中current_index=1因爲我們已經處理過的索引= 0，並決定將忽略它，而且MIN_VAL是我們上面
提到以第一數量的小的值。假設它的值是X.那麼結果是X + sum(1, X)。這意味着解決方案包含X，因爲您決定將其包含在序列中，以及結果來自sum(1,X)。請注意，我們調用總和與MIN_VAL=X因爲我們決定採取X，讓我們選擇下面的值必須大於X.

這兩項決定是有效的更大。結果是這兩者的最大值。因此，我們可以推斷，一般復發，如下：

sum(current_index, MIN_VAL) = max( sum(current_index + 1, MIN_VAL) // ignore, seq[current_index] + sum(current_index + 1, seq[current_index]) // take )。

第二個決定並不總是有效，因此您必須確保當前元素> MIN_VAL纔能有效接受它。

這是想法僞代碼：

你指出

sum(current_index, MIN_VAL){ 
    if(current_index == END_OF_SEQUENCE) return 0 
    if(state[current_index,MIN_VAL] was calculated before) return the perviously calculated result 

    decision_1 = sum(current_index + 1, MIN_VAL) // ignore case 
    if(sequence[current_index] > MIN_VAL) // decision_2 is valid 
     decision_2 = sequence[current_index] + sum(current_index + 1, sequence[current_index]) // take case 
    else 
     decision_2 = INT_MIN 

    result = max(decision_1, decision_2) 
    memorize result for the state[current_index, MIN_VAL] 
    return result 
}

來源

2017-07-02 04:52:43

Intresting測試用例。讓我重做這個並回來。你的僞代碼類似於類似的解決方案，以改變硬幣或類似的問題，這需要你選擇一個價值的道路，並詳盡搜索餘下的回溯 –

它是相似的，除了你不會窮盡搜索，因爲記憶會切斷很多不需要的探索。讓我知道你是否需要更多的幫助。 –

最高金額遞增子，改變算法使用記憶化

回答

相關問題