最大子數組（Kadane算法） - 尾遞歸

Question

我想在Prolog中實現Kadane's Algorithm。 其中一個要求是尾部調用（遞歸）。

我嘗試了很多可能性，但沒有成功。 這裏是我的代碼：

max_sum(L, S) :- 
    S is 0, 
    H is 0, 
    max_sum(L, H, S). 

max_sum([], S, S). 
max_sum([X | L], H, S) :- 
    ( H + X < 0 -> NewH is 0; NewH is H + X), 
    ( S < H + X -> NewS is NewH; NewS is S), 
    length(L, N), 
    ( N < 1 -> max_sum(L, NewS, NewS); max_sum(L, NewH, NewS)). 

NewH，新聞是溫度值（我們不能在序言兩次分配一個值吧？）。 我可以要求提示嗎？

編輯：

[trace] ?- max_sum([1, 2, 3], S). 
    Call: (7) max_sum([1, 2, 3], _G8907) ? creep 
    Call: (8) _G8907 is 0 ? creep 
    Exit: (8) 0 is 0 ? creep 
    Call: (8) _G8991 is 0 ? creep 
    Exit: (8) 0 is 0 ? creep 
    Call: (8) max_sum([1, 2, 3], 0, 0) ? creep 
    Call: (9) 0+1<0 ? creep 
    Fail: (9) 0+1<0 ? creep 
    Redo: (8) max_sum([1, 2, 3], 0, 0) ? creep 
    Call: (9) _G8994 is 0+1 ? creep 
    Exit: (9) 1 is 0+1 ? creep 
    Call: (9) 0<0+1 ? creep 
    Exit: (9) 0<0+1 ? creep 
    Call: (9) _G8997 is 1 ? creep 
    Exit: (9) 1 is 1 ? creep 
    Call: (9) length([2, 3], _G8998) ? creep 
    Exit: (9) length([2, 3], 2) ? creep 
    Call: (9) 2<1 ? creep 
    Fail: (9) 2<1 ? creep 
    Redo: (8) max_sum([1, 2, 3], 0, 0) ? creep 
    Call: (9) max_sum([2, 3], 1, 1) ? creep 
    Call: (10) 1+2<0 ? creep 
    Fail: (10) 1+2<0 ? creep 
    Redo: (9) max_sum([2, 3], 1, 1) ? creep 
    Call: (10) _G9000 is 1+2 ? creep 
    Exit: (10) 3 is 1+2 ? creep 
    Call: (10) 1<1+2 ? creep 
    Exit: (10) 1<1+2 ? creep 
    Call: (10) _G9003 is 3 ? creep 
    Exit: (10) 3 is 3 ? creep 
    Call: (10) length([3], _G9004) ? creep 
    Exit: (10) length([3], 1) ? creep 
    Call: (10) 1<1 ? creep 
    Fail: (10) 1<1 ? creep 
    Redo: (9) max_sum([2, 3], 1, 1) ? creep 
    Call: (10) max_sum([3], 3, 3) ? creep 
    Call: (11) 3+3<0 ? creep 
    Fail: (11) 3+3<0 ? creep 
    Redo: (10) max_sum([3], 3, 3) ? creep 
    Call: (11) _G9006 is 3+3 ? creep 
    Exit: (11) 6 is 3+3 ? creep 
    Call: (11) 3<3+3 ? creep 
    Exit: (11) 3<3+3 ? creep 
    Call: (11) _G9009 is 6 ? creep 
    Exit: (11) 6 is 6 ? creep 
    Call: (11) length([], _G9010) ? creep 
    Exit: (11) length([], 0) ? creep 
    Call: (11) 0<1 ? creep 
    Exit: (11) 0<1 ? creep 
    Call: (11) max_sum([], 6, 6) ? creep 
    Exit: (11) max_sum([], 6, 6) ? creep 
    Exit: (10) max_sum([3], 3, 3) ? creep 
    Exit: (9) max_sum([2, 3], 1, 1) ? creep 
    Exit: (8) max_sum([1, 2, 3], 0, 0) ? creep 
    Exit: (7) max_sum([1, 2, 3], 0) ? creep 

在呼叫（11），我有從這個簡單的例子良好的結果（6）。我該如何結束這個功能而不返回？這是我的問題。從該代碼

結果是S = 0，而不是S = 6.

最終編輯（工作代碼）：

max_sum(L, S) :- 
    max_sum(L, 0, 0, S). 

max_sum([], _, S, S). 
max_sum([X | L], H, F, S) :- 
    NewH is max(0, H + X), 
    (F < H + X -> NewF is NewH; NewF is F), 
    max_sum(L, NewH, NewF, S). 

其中：

• 的S - 最終結果，
• F - maximum_so_far，
• H - maximum_ending_here，
• X - 列表頭，
• L - 列表，
• NewH，NewF - 臨時值。

感謝您的幫助:)

Answer 1

我建議@Repeat提出的solution的稍加改動版本：

:- use_module(library(clpfd)). 

zs_max([Z|Zs], MSF) :- 
    zs_max_(Zs, Z, Z, MSF). 

zs_max_([], _, MSF, MSF). 
zs_max_([Z|Zs], MEH0, MSF0, MSF) :- 
    max(Z, MEH0+Z) #= MEH1, 
    max(MSF0, MEH1) #= MSF1, 
    zs_max_(Zs, MEH1, MSF1, MSF). 

首先，從原來的solution樣品的查詢產生相同的結果：

?- zs_max([-2,1,-3,4,-1,2,1,-5,4], Max). 
Max = 6 
    ?- zs_max([-2,3,4,-5,8,-12,100,-101,7], Max). 
Max = 100 

然而，這個版本更通用，因爲它可以使用任意值（如在solution的評論中@false所建議的那樣）。這是通過與列表而不是0的第一個元素的值開始來完成因此，以下查詢產生不同的結果：

?- zs_max([-2,-3,-4], X). 
X = -2 
    ?- zs_maxmum([-2,-3,-4], X). 
X = 0 

另一個區別是，空的列表沒有溶液：

?- zs_max([], X). 
no 
    ?- zs_maxmum([], X). 
X = 0 

我認爲這種行爲更合理，因爲空列表沒有子列表，因此沒有從中選擇最大值的子列表總和。但是，如果需要，可以輕鬆添加空列表的特殊情況：

zs_max([], replaceThisWithAReasonableValue). 

Answer 2

標準的方法是添加一個輸出參數，遞歸停止時得到統一。像

max_sum(L, S) :- 
    max_sum(L, 0, 0, S). 

max_sum([], _, S, S). 
... 

東西之後，你的代碼的方式複雜得多，需要：在維基百科上列出的兩個版本不需要任何測試或長/ 2計算。 試圖簡化它，只留下計算（可以使用例如Max_ending_here is max(0, H + X),和尾遞歸調用。

Answer 3

1. 這個問題，其實是一個的 「Finding the maximum sublist in Prolog」一式兩份。

2. 有被賞金供，所以

3. 我建議使用它不能被標記爲重複。我previous solution —它是基於clpfd，並與SWI-Prolog的運行。