这个答案显示了 Prolog 端口卡丹算法 /questions/tagged/kadanes-algorithm基于clpfd /questions/tagged/clpfd:
:- use_module https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/mpg_002dref_002duse_005fmodule.html(library https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/The-Prolog-Library.html#The-Prolog-Library(clpfd https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/lib_002dclpfd.html)).
我们定义zs_maxmum/2
像这样:
zs_maxmum(Zs, MSF) :-
zs_maxmum_(Zs, 0,_, 0,MSF).
zs_maxmum_([], _,_, MSF,MSF).
zs_maxmum_([Z|Zs], MEH0,MEH, MSF0,MSF) :-
max(0,MEH0+Z) #= MEH1,
max(MSF0,MEH1) #= MSF1,
zs_maxmum_(Zs, MEH1,MEH, MSF1,MSF).
示例查询:
?- zs_maxmum([-2,1,-3,4,-1,2,1,-5,4], Max).
Max = 6.
?- zs_maxmum([-2,3,4,-5,8,-12,100,-101,7], Max).
Max = 100.
几点说明:
- 我们实际上并不是对数组进行操作,而是对lists.
- 我们承认任意子列表,包括
[]
。目标zs_maxmum([-2,-3,-4], 0)
成功了。