[Jprogramming] Maximum Subarray Problem

[Raul Miller]

Might be worth adding to
https://rosettacode.org/wiki/Greatest_subsequential_sum#J ?

Thanks,

—
Raul

On Sunday, February 24, 2019, 'Jon Hough' via Programming <
programming at jsoftware.com> wrote:

> Reference: https://en.wikipedia.org/wiki/Maximum_subarray_problem
>
> This is the problem:
> Given an array of numbers, find the contiguous subset of maximum sum. i.e.
> find the maximum sum subarray.
> Example:
> R=: 3 4 _5 2 1 1
> The maximum subarray is 3 4
>
> Kadane's algorithm is a linear time algorithm to solve this. Rather than
> explicitly implementing this, I wanted a J verb to solve this, using J
> primitives.
>
> I wrote a horrendously long one-liner to solve this:
> f=: ({.@:I.@:(= >./)@:>@:({:&.>) { ])@:(>:@:i.@:# (({.@:I.@:(= >./) ([ ,
> {) ])@:(+/\) <@,~ [)"0 _ ]) ((i.@:{. + {:)@:}:@:,@:>@:[ { ]) ]
>
> Empirically, I found this to be O(n) in time. e.g.
> For an array of length 8000
> timespacex gives:              0.25468 3.40134e6
> For array of length 16000: 1.03293 6.80102e6
> For array of length 32000: 4.09139 1.36004e7
> For array of length 64000: 16.3896 2.71991e7
>
> Any better solutions (faster, and more elegant)?
>
> Thanks,
> Jon
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm