Rosetta: Greatest subsequential sum

Path	csiph.com!aioe.org!.POSTED!not-for-mail
From	"Robert L." <No_spamming@noWhere_7073.org>
Newsgroups	comp.lang.forth
Subject	Rosetta: Greatest subsequential sum
Date	Fri, 21 Apr 2017 20:57:21 +0000 (UTC)
Organization	Aioe.org NNTP Server
Lines	61
Message-ID	<oddrnf$g72$1@gioia.aioe.org> (permalink)
NNTP-Posting-Host	K9Swgy92kr/Q9Q3ptxCUUw.user.gioia.aioe.org
Mime-Version	1.0
Content-Type	text/plain; charset=iso-8859-1
X-Complaints-To	abuse@aioe.org
User-Agent	XanaNews/1.18.1.6
X-Notice	Filtered by postfilter v. 0.8.2
Xref	csiph.com comp.lang.forth:57750

Show key headers only | View raw

> Given a sequence of integers, find a continuous subsequence
> which maximizes the sum of its elements, that is, the elements
> of no other single subsequence add up to a value larger than
> this one.
> 
> An empty subsequence is considered to have the sum of   0;
> thus if all elements are negative, the result must be the
> empty sequence.


> 2variable best
> variable best-sum
>  
> : sum ( array len -- sum )
>   0 -rot cells over + swap do i @ + cell +loop ;
>  
> : max-sub ( array len -- sub len )
>   over 0 best 2!  0 best-sum !
>   dup 1 do                  \ foreach length
>     2dup i - 1+ cells over + swap do   \ foreach start
>       i j sum
>       dup best-sum @ > if
>         best-sum !
>         i j best 2!
>       else drop then
>     cell +loop
>   loop
>   2drop best 2@ ;
>  
> : .array  ." [" dup 0 ?do over i cells + @ . loop ." ] = " sum . ;
>  
> create test  -1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1 ,
> create test2 -1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , 99 ,
> Output:
> test 11 max-sub .array [3 5 6 -2 -1 4 ] = 15 ok
> test2 11 max-sub .array [3 5 6 -2 -1 4 -4 2 99 ] = 112 ok


def best ary
  x = Enumerator.new{|y|
    ary.size.times{|i| 0.upto(ary.size - i){|j| y.yield ary[i,j] }}
  }
  x.max_by{|a| a.reduce(0,:+)}
end


best [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
    ==>[3, 5, 6, -2, -1, 4]

best [-1, -2, -3, -5, -6, -2, -1, -4, -4, -2, -1]
    ==>[]

best [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, 99]
    ==>[3, 5, 6, -2, -1, 4, -4, 2, 99]


-- 
In cases of gang rape, ... the perpetrators are ... mostly from Muslim
countries....  Several times the courts have acquitted suspects who have
claimed that the girl wanted sex with six, seven, or eight men.
thenewamerican.com/world-news/europe/item/20142-cover-up-the-swedish-left-s-sacrifice-of-women-to-political-correctness

Back to comp.lang.forth | Previous | Next | Find similar | Unroll thread

Thread

Rosetta: Greatest subsequential sum "Robert L." <No_spamming@noWhere_7073.org> - 2017-04-21 20:57 +0000

csiph-web