Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #57750 > unrolled thread

Rosetta: Greatest subsequential sum

Back to article view | Back to comp.lang.forth

Contents

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

#57750 — Rosetta: Greatest subsequential sum

> 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

[toc] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web