最大子数组（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, 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

标准方法是添加一个输出参数，当递归停止时统一。像

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

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

然后，您的代码比需要的复杂得多：维基百科上列出的两个版本都不需要任何测试或 length/2 计算。尝试简化它，只留下计算（例如，您可以使用 Max_ending_here is max(0, H + X), 和尾递归调用。

Answer 2

这个问题实际上是重复的 “Finding the maximum sublist in Prolog”.
有悬赏，因此不能将其标记为重复。
我建议使用我的 previous solution—it is based on clpfd 并使用 SWI-Prolog 运行。

Answer 3

我提议对@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

然而这个版本更通用，因为它适用于任意值（正如@false 在对 solution 的评论中所建议的）。这是通过从列表的第一个元素的值而不是 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).

最大子数组（Kadane 算法）- 尾递归

Maximum Subarray (Kadane's algorithm) - Tail recursion

prolog

tail-recursion

kadanes-algorithm