prolog - 最大子数组(Kadane 算法)- 尾递归

Question

我正在尝试实现 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, NewS 是临时值(我们不能在 Prolog 中赋值两次，对吗？)。我可以请求提示吗？

编辑:

[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

在 Call(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

1. 这个问题实际上是"Finding the maximum sublist in Prolog "。

2. 有人为其提供赏金，因此不能将其标记为重复。

3. 我建议使用我的 previous solution —它基于 clpfd并使用 SWI-Prolog 运行。