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

Groups > comp.lang.forth > #57750

Rosetta: Greatest subsequential sum

Show all headers | 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