在Prolog中找到最大的子列表 [英] Finding the maximum sublist in Prolog

问题描述

我是Prolog的新手，并试图解决最大子数组问题的实例.

I'm new to Prolog and trying to solve instances of the maximum subarray problem.

我有以下非常优雅的C ++代码:

I have got the following quite elegant C++ code:

int maxSubArray(vector<int> List)
{
    int maxsofar = 0;
    int maxendinghere = 0;
    for (int i = 0; i < List.size(); i++)
    {
        maxendinghere = max(maxendinghere+List[i], 0);
        maxsofar = max(maxsofar, maxendinghere);
    }
    return maxsofar;
}

这是我的Prolog代码:

And here is my Prolog code:

max(X,X,X).
max(X,Y,X) :- X>Y.
max(X,Y,Y) :- X<Y. %define max function

prev(L,T,H) :-
   reverse(L,[H|T1]),
   reverse(T,T1).  %split L to H(last element) and T(the remaining list)

f([],0,0).
f(L,M,N) :-
   f(L1,M1,N1),
   prev(L,L1,E),
   max(M1,N,M),
   max(K,0,N), 
   K is N1+E.

我尝试从f(L,M,N)中获取最大和，其中L是列表，M是结果(最大和，也类似于C ++代码中的变量"maxsofar")，我想获取N是中间变量，在C ++代码中为"maxendinghere".我想从以前的列表L1中获得L的答案，并且变量的关系与C ++代码相同.

I try to get the maximum sum from f(L,M,N), where L is the list, M is the result (maximum sum, also like the variable "maxsofar" in C++ code) I want to get, N is a intermediary variable as the "maxendinghere" in C++ code. I want to get answer of L from its former list L1, and the relation of variables are just the same as the C++ code.

但是，以下查询不起作用:

However, the following query does not work:

?- f([1,2,3],X,Y).
is/2: Arguments are not sufficiently instantiated

我不知道问题出在哪里.

I don't know where the problem is.

推荐答案

此答案显示了 kadanes-algorithm 根据clpfd :

:- use_module(library(clpfd)).

我们这样定义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.

一些说明:

• 我们实际上不是在数组上操作，而是在列表上操作.
• 我们接受任意子列表，包括[].目标zs_maxmum([-2,-3,-4], 0)成功.

• We don't actually operate on arrays, but on lists.
• We admit arbitrary sublists, including []. The goal zs_maxmum([-2,-3,-4], 0) succeeds.

这篇关于在Prolog中找到最大的子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！