## Introduction

Through the ArrayCast podcasts I became aware of this interesting algorithm. https://www.arraycast.com/episode-8-show-notes

The problem statement is relatively simple:

Given a list of numbers, find the largest sum produced by any of the possible contiguous subsequences

The test case: Given: _2 1 _3 4 _1 2 1 _5 4
Find: the maximum partial sum

Conor Hoekstra a C++ developer and one of the hosts of ArrayCast. He had become interested in APL. On his twitter account he Tweeted about an elegant solution in APL (link available at the show notes link above). If it worked it was rather elegant, however, it turned out to be incorrect.

This is the combination that looked as though it would implement the Kadane algorithm:

myvec←¯2 1 ¯3 4 ¯1 2 1 ¯5 4
myvec
¯2 1 ¯3 4 ¯1 2 1 ¯5 4
⌈/(⊢⌈+)\ myvec
12

⍝ In APL the +\ operator performs a scan reduce
⍝ it produces prefixes of its arguments and automatically
⍝ does a + reduce on that prefix
⍝ ⍳5 will produce the vector 1 2 3 4 5
+\⍳5
1 3 6 10 15

⍝ By the answer alone you may come up with the false
⍝ impression that an accumulate function is occuring.
⍝ In the '+' case that would be 'current element' + 'previous sum' as
⍝ the vector is traversed.
⍝ In fact no such accumulate occurs for each answer it sums the partial vector so far

⍝ In J this same scan-reduce functionality is accomplished by '+/\'

The simple problem statement makes it a great example to use for a J tutorial. The rest of this essay is just that, a tutorial using simple easy to understand operators (called verbs in J) that morphed into an introduction of an advanced features of J known as "tacit" programming. Tacit programming is the combining of verbs (operators) together in various ways to form powerful programs. This is part of a more general concept of function combinators used in combinatory logic (see https://en.wikipedia.org/wiki/Combinatory_logic).

## J Symbols Used/Needed

The following is the subset of J verbs and adverbs (built in functions ) used to program a solution to the maximum sum problem and the Kadane Algorithm. There are also symbols used as support operators. Some to investigate how combinations of operators behave. Others to select an intermediate solution to verify that the J code is processing the numbers correctly.

A brief description of each symbol and its web page from the J NuVoc (the J vocabulary webpage) are provided. NuVoc is not so new any more. It's probably one of the best language references for any programming language that I have seen. The main NuVoc page is here: https://code.jsoftware.com/wiki/NuVoc

A quick word about the J code provided: be sure to read the comments (lines with 'NB.' the comment delimiter in J). I use programming comments to explain "in-line" within the source code, rather than to come back out into wiki media text.

### =: - assignment

Just like any other programming language you can assign values to a variable. In J numbers in the form of a space separated list are the basis for the language. I tend to use list, array, and vector interchangably.

myvec =: _2 1 _3 4 _1 2 1 _5 4
myvec
_2 1 _3 4 _1 2 1 _5 4

NB. Monadic plus is the complex conjugate of a value.
NB. For real numbers it just returns the number (there is no complex value involved)
NB. I mention this because I mistakenly ended up apply
NB. the monadic form of plus. In my case its due to
NB. previous APL knowledge and forgetting that J is not
NB. a direct rewrite of APL and some operators that look
NB. the same operate differently.
+ 4.5
4.5
+ 4.5j6
4.5j_6

NB. dydactic case it works the way you would expect
1 + 2
3
1 + 2 3 4
3 4 5
1 2 3 + 4 5 6
5 7 9

NB. addition works for scalar + vector
NB. but vector + vector must have the same length and/or shape
1 2 + 3 4 5
|length error
|   1 2    +3 4 5

The other base arithmetic operators have the expected dyadic usage. I won't introduce in a separate heading as they are used only as examples and are not used in the direct calculation of the Maximum sum problem.

NB. like other programming languages * and - are multiplication and subtraction respectively
5 - 2
3
5 * 2
10

NB. division uses the ascii percent sign ('%') as the major difference to most other languages
10 % 2
5

### >. - ceiling/maximum

NB. Only the dyadic case is used for >.
3 >. 5
5
5 >. 3
5

### # - tally/vector length

NB. myvec has 9 elements defined
myvec
_2 1 _3 4 _1 2 1 _5 4

NB. # returns the length/count/'tally' of the number of elements
# myvec
9

### < - box/less than

<1
┌─┐
│1│
└─┘
< 1 3 4
┌─────┐
│1 3 4│
└─────┘
<'hello'
┌─────┐
│hello│
└─────┘

I am only using the monadic boxing functionality it also represents mathematical less than operator when used in its dyadic form

### ; - another box operator

'hello';1 3 4
┌─────┬─────┐
│hello│1 3 4│
└─────┴─────┘

NB. monadic case it removes boxes
1;2;3
┌─┬─┬─┐
│1│2│3│
└─┴─┴─┘
;(1;2;3)
1 2 3
1 2 3; 1 2 3 4;5 4 3 2 1
┌─────┬───────┬─────────┐
│1 2 3│1 2 3 4│5 4 3 2 1│
└─────┴───────┴─────────┘

Boxing allows you to concatenate different data types into a single array/vector. It also allows different length arrays to be collected into a single array. The latter is the functionality utilized in this investigation.

### ] - display right operator

The right bracket is an operator that will return the value of its right operand. It may seem a like a silly operator to those familiar with other languages. But it plays an important role as a short hand for displaying results from an assignment and when we want to use complex combinations of operators and move the right hand operand into various portions of a sequence of operations. It is also helpful for finding out how adverbs act on a list of numbers. Below I show the simple usage of the operator (verb).

myvec
_2 1 _3 4 _1 2 1 _5 4
]myvec =: _2 1 _3 4 _1 2 1 _5 4
_2 1 _3 4 _1 2 1 _5 4
2 ] 4
4

### [ - display left operator

The same as the display right but operates on the left hand side value/operand.

1 [ 2
1

### { - select

J does not use brackets to select array/vector elements. Brackets to select elements of arrays do not fit the operator-operand or operand-operator-operand style of J. So instead of using brackets like other languages element selection has its own verb '{' the left brace.

0 { 2 4 6 8
2
1 { 2 4 6 8
4
2 { 2 4 6 8
6
3 { 2 4 6 8
8

The reduce adverb inserts the verb on the left of the '/'(slash) in between each of the elements and then evaluates. This is very handy way of summing all the elements of an array/vector using '+/'. It is a very powerful short hand and saves you from writing functions with loops to obtain simple functionality with verbs(operators) already defined in J.

1 + 2 + 3 + 4 + 5
15
+/ 1 2 3 4 5       NB. J actually inserts the operator then evaluates
15

NB. the above are effectively equivalent forms

NB. it works with the maximum/ceiling operator as well
5 >. 6 >. 8 >. 2 >.3
8
>./ 5 6 8 2 3
8

NB. prefix operator needs a verb to operate with
NB. lets use the ] right display just to see how
NB. it divies up the array argument
]\ 1 2 3 4 5
1 0 0 0 0
1 2 0 0 0
1 2 3 0 0
1 2 3 4 0
1 2 3 4 5

NB. it pads with 0s to make the output regular which
NB. is why I usually use the box operator to give a
NB. a more acurate accounting of the output
<\ 1 2 3 4 5
┌─┬───┬─────┬───────┬─────────┐
│1│1 2│1 2 3│1 2 3 4│1 2 3 4 5│
└─┴───┴─────┴───────┴─────────┘

This operator is the same symbol as the scan operator in APL and while the functionality is similar the J implementation only provides prefixes. It is up to the programmer to choose how to process those prefixes. In APL the operator combines prefixes with a reduce operation. More on this where I make my mistake with this operator.

NB. the suffixes operator works similarly
]\. 1 2 3 4 5
1 2 3 4 5
2 3 4 5 0
3 4 5 0 0
4 5 0 0 0
5 0 0 0 0
<\. 1 2 3 4 5
┌─────────┬───────┬─────┬───┬─┐
│1 2 3 4 5│2 3 4 5│3 4 5│4 5│5│
└─────────┴───────┴─────┴───┴─┘

### ? - roll operator

?10    NB. returns a random number from the 10 number range 0 - 9
6
?10
3
?10 10 10        NB. works on arrays too
9 0 3

### \$ - shape operator

NB. shape lets me create arrays from a single value
10\$5
5 5 5 5 5 5 5 5 5 5
5\$10
10 10 10 10 10

There is much more to this operator but this simple dyadic usage is all I need for creating a large test case to get runtime timings of the routines developed here.

### each (&.>) - each conjunction

The 'each' conjunction is fairly self explanatory. It takes an operator and applies it to the elements of each boxed item. Most of the functionality has to do with the under conjunction '&.'. 'each' will unbox an item apply the operator on the left hand side and rebox the result. It will reform the result keeping the same number of boxes as were in the original right hand operand. An example reveals the functionality better than my explanation.

1 2 3; 1 2 3 4;5 4 3 2 1
┌─────┬───────┬─────────┐
│1 2 3│1 2 3 4│5 4 3 2 1│
└─────┴───────┴─────────┘
+/ each 1 2 3; 1 2 3 4;5 4 3 2 1
┌─┬──┬──┐
│6│10│15│
└─┴──┴──┘

### & - bond conjunction

This conjunction enables the 'bonding' of a constant or variable ('noun' in J parlance) to an operator

2&+ 1 2 3
3 4 5
myvec&+ 5
3 6 2 9 4 7 6 0 9
myvec+5
3 6 2 9 4 7 6 0 9

This will come in handy when creating other combinators such as the fork which is used to solve the maximum sum problem.

### @ - atop conjunction

This conjunction places one function 'atop' of another. It enforces the order in which the operators will process an argument. It will apply the right most operator to the operand first and then apply the left operator to the answer.

NB. to demonstrate '@' with a trivial example
NB. demonstrate '@' with a trivial example
4 4\$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16

NB. to sum the columns just use '+/' the sum conjunction
+/4 4\$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
28 32 36 40

NB. to find the highest sum of the columns use
NB. the maximum conjunction '>./'
>./ +/4 4\$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
40

NB. '@' (atop) is needed to tell J the specific order of
NB. of applying these operators
(>./)@(+/)4 4\$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
40

NB. Here there is no difference really but if this
NB. combination were to be saved in a variable to
NB. provide easy reuse and give it a name '@' (atop)
NB. becomes important
maxcol =: >./ +/
maxcol 4 4\$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
28 32 36 40
28 32 36 40
28 32 36 40
28 32 36 40

28 32 36 40
28 32 36 40
28 32 36 40
28 32 36 40

28 32 36 40
28 32 36 40
28 32 36 40
28 32 36 40

28 32 36 40
28 32 36 40
28 32 36 40
28 32 36 40

NB. J interprets this as a combinator called a hook
NB. this will be left to the reader to research since
NB. this feature is not used further.
NB. to force J to turn off the hook interpretation
NB. maxcol is defined as follows:
maxcol =: (>./)@(+/)
maxcol 4 4\$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
40

NB. atop has a certain enforcement in the order of
NB. operations that is different than just stringing
NB. operators together

J has many ways of combining operations to help simplify function definition. Therefore it also has ways such as '@' atop to allow the user to control how the operators are used in combination with the operands. This is both part of the elegance of J and a source of its complexity. This combinator functionality is introduced because it highlights how many different ways you can accomplish a simple task in J using a relatively small number of J operators while taking advantage of J's more complex features

### fork combinator

The fork combinator allows the user to combine 3 operators in a certain way. There are 2 basic forms, a monadic and dyadic form:

NB. (f g h) myvec   <==> (f myvec) g (g myvec)
NB.
NB. x (f g h) myvec  <==> (x f myvec) g (x h myvec)

This may seem quite arbitrary but it turns out that it helps to concisely express certain simple functions. The most common example is an average function:

(5 + 3) * (5 - 3)
16
5 (+ * -)3
16

NB. The most famous fork is for averaging numbers (+/ % #) it uses the monadic form of each verb
NB. to create a monadic fork
NB. In English pseudocode it does the following: (sum a list of numbers) and divide by (length of list of numbers)
(+/ % #) 1 2 3 4 5
3
(+/ 1 2 3 4 5) % (# 1 2 3 4 5)
3

### J function definition

https://code.jsoftware.com/wiki/Vocabulary/com https://code.jsoftware.com/wiki/Vocabulary/DirectDefinition J allows explicit definition of nouns, verbs and adverbs. Only monadic verb definition is used here. The typical ways to define a monadic verb (i.e. takes only a right hand side argument) are shown. J has a cryptic single line and multiline method: 3 : '<J statement here with a y argument>' or 3 : 0 <followed by multiline J statements> ). The right parenthesis ')' signifies the end of a multiline definition.

It is easier to show than to explain:

myfunc =: 3 : 0
NB. place J statements in here to define function
NB. the variable 'y' is the right hand argument to this
NB. function
)
myfunc
3 : 0
NB. place J statements in here to define function
NB. the variable 'y' is the right hand argument to this
NB. function
)
NB. variables defined to represent the 3 : 0 base definition
)
myfunc1       NB. end up with same type of definition
3 : 0
NB. variables defined to represent the 3 : 0 base definition
)

myOneLineFunc =: 3 : 'y'
myOneLineFunc
3 : (,'y')
myOneLineFunc 3
3

NB. the new dnfs way of function definition
myfunc2 =: {{y}}
myfunc2
3 : (,'y')
myfunc2 3
3

## Naive brute force solution of the problem

Before addressing the Kadane algorithm specifically, the following is a brute force solution. This generates all the possible subsequences and sums them and then picks out the maximum sum.

NB. First I thought to box suffixes of myvec
myvec =: _2 1 _3 4 _1 2 1 _5 4

<\.myvec
┌─────────────────────┬──────────────────┬────────────────┬─────────────┬───────────┬────────┬──────┬────┬─┐
│_2 1 _3 4 _1 2 1 _5 4│1 _3 4 _1 2 1 _5 4│_3 4 _1 2 1 _5 4│4 _1 2 1 _5 4│_1 2 1 _5 4│2 1 _5 4│1 _5 4│_5 4│4│
└─────────────────────┴──────────────────┴────────────────┴─────────────┴───────────┴────────┴──────┴────┴─┘

NB. then run partial sums on each of the suffixes
+\ each <\.myvec
┌─────────────────────┬──────────────────┬────────────────┬─────────────┬───────────┬────────┬──────┬────┬─┐
│_2 0  0 0  0 0 0  0 0│1  0 0  0 0 0  0 0│_3 0  0 0 0  0 0│4  0 0 0  0 0│_1 0 0  0 0│2 0  0 0│1  0 0│_5 0│4│
│_2 1  0 0  0 0 0  0 0│1 _3 0  0 0 0  0 0│_3 4  0 0 0  0 0│4 _1 0 0  0 0│_1 2 0  0 0│2 1  0 0│1 _5 0│_5 4│ │
│_2 1 _3 0  0 0 0  0 0│1 _3 4  0 0 0  0 0│_3 4 _1 0 0  0 0│4 _1 2 0  0 0│_1 2 1  0 0│2 1 _5 0│1 _5 4│    │ │
│_2 1 _3 4  0 0 0  0 0│1 _3 4 _1 0 0  0 0│_3 4 _1 2 0  0 0│4 _1 2 1  0 0│_1 2 1 _5 0│2 1 _5 4│      │    │ │
│_2 1 _3 4 _1 0 0  0 0│1 _3 4 _1 2 0  0 0│_3 4 _1 2 1  0 0│4 _1 2 1 _5 0│_1 2 1 _5 4│        │      │    │ │
│_2 1 _3 4 _1 2 0  0 0│1 _3 4 _1 2 1  0 0│_3 4 _1 2 1 _5 0│4 _1 2 1 _5 4│           │        │      │    │ │
│_2 1 _3 4 _1 2 1  0 0│1 _3 4 _1 2 1 _5 0│_3 4 _1 2 1 _5 4│             │           │        │      │    │ │
│_2 1 _3 4 _1 2 1 _5 0│1 _3 4 _1 2 1 _5 4│                │             │           │        │      │    │ │
│_2 1 _3 4 _1 2 1 _5 4│                  │                │             │           │        │      │    │ │
└─────────────────────┴──────────────────┴────────────────┴─────────────┴───────────┴────────┴──────┴────┴─┘

NB. This didn't work the way I expected
NB. +\ is not producing partial sums it appears to display just the subsequences
NB. this is because the monadic '+' is being applied which performs a complex conjugate
NB. that returns just the integer in question
NB. +/ (summation of a vector in J) is the operator that needs to be used
NB. this will sum prefixes of each of the suffixes generated
+/\each <\.myvec
┌──────────────────────┬─────────────────┬───────────────┬───────────┬───────────┬────────┬──────┬─────┬─┐
│_2 _1 _4 0 _1 1 2 _3 1│1 _2 2 1 3 4 _1 3│_3 1 0 2 3 _2 2│4 3 5 6 1 5│_1 1 2 _3 1│2 3 _2 2│1 _4 0│_5 _1│4│
└──────────────────────┴─────────────────┴───────────────┴───────────┴───────────┴────────┴──────┴─────┴─┘

NB. You can verify by hand that each of these is the partial sum for each
NB. subsequence I generated when I obtained the suffixes
NB. for example taking the 3rd suffix (indexed from 0 we select index 2)
2 { <\.myvec
┌────────────────┐
│_3 4 _1 2 1 _5 4│
└────────────────┘

NB. select out the 2 index from the partial sums
2 { +/\each <\.myvec
┌───────────────┐
│_3 1 0 2 3 _2 2│
└───────────────┘
NB. _3 is the first element of the partial sum
NB. 1 is the next (_3 + 4)
NB. 0 is next (_3 + 4 + 1)
NB. 2 (_3 + 4 + 1 + 2)
NB. 3 (_3 + 4 + 1 + 2 + 1)
NB. _2 (_3 + 4 + 1 + 2 + 1 + _5)
NB. finally 2 (_3 + 4 + 1 + 2 + 1 + _5 + 4)

NB. To get to a final answer I need to unbox this at some point
NB. so why not just unbox everything right away then I can
NB. find the Maximum of the combined sums and have my answer

NB. applying ; monadically removes the boxes and appends all the contents together
; +/\each <\.myvec
_2 _1 _4 0 _1 1 2 _3 1 1 _2 2 1 3 4 _1 3 _3 1 0 2 3 _2 2 4 3 5 6 1 5 _1 1 2 _3 1 2 3 _2 2 1 _4 0 _5 _1 4

NB. applying the >./ verb/adverb combination finds the greatest sum calculated
>./ ; +/\each <\.myvec
6

## Refactoring

I tend to use boxing to help step through a problem especially with operators that I know will return different length answers. The boxing preserves the individual lengths as J will 'pad' answers to form them into a single matrix format.

When programming in J in this fashion (over boxed elements) one of the "smell" tests that the code can be condensed is when there are serial each statements applying one operator at a time. Intuitively why would J go through all the trouble to provide these operators if boxing has to be done on simple array/lists? The answer is it wouldn't. The boxing is now getting in the way of more basic J array processing. The next step is to remove boxing from this J code.

NB. the other way I thought of doing this was as follows:
>./ each +/\each <\.myvec
┌─┬─┬─┬─┬─┬─┬─┬──┬─┐
│2│4│3│6│2│3│1│_1│4│
└─┴─┴─┴─┴─┴─┴─┴──┴─┘

NB. apply max on each of the boxed answers and then unbox and perform the
NB. final maximum.
>./ ; >./ each +/\each <\.myvec
6

NB. once I see 2 'each's applied serially I know I should be able to start
NB. combining operations:
(>./@(+/\)) each <\.myvec
┌─┬─┬─┬─┬─┬─┬─┬──┬─┐
│2│4│3│6│2│3│1│_1│4│
└─┴─┴─┴─┴─┴─┴─┴──┴─┘

NB. In hind sight it would seem obvious that you can just remove the boxing
NB. since the intermediate answers are all the same size. However for some reason
NB. it took me quite a while to realize this. Rather than bore you with my
NB. feeble attempts. Just delete the each and the box operator and let the
NB. combined operations work directly on the suffixes
(>./@(+/\))\.myvec
2 4 3 6 2 3 1 _1 4

NB. Now apply the >./ (maximum reduction)
>./(>./@(+/\))\.myvec
6

NB. as I was editing this write up I realized there is a fork implementation
NB. of the above J code
>./([: >./ (+/\))\.myvec
6

NB. I was using the atop '@' to force the order of the applied operators
NB. It hit me this is just a fork with a cap '[:' to make sure the
NB. right hand argument is not fed in as a dydactic operand
NB. I believe they went over all this in an Array Cast episode but I
NB. had to code it before it all came together in my head

The Kadane Algorithm calculates local maximums (for lack of a better term). As the array is traversed either the number or the currently running sum will be the new maximum. If the actual element is the greater than the newly calculated local maximum (current element + previous calculated local maximum), then the current element is chosen. This resets the running sum to start from this latest element. In essence the algorithm has located a start of a new subsequence that could potentially be the maximum sum subsequence.

For example, in a sequence of all negative numbers except 1 number that is positive. That single positive number will be the highest sum of any of the subsequences calculated from 2 or more values. None of the numbers around that number are going to improve the sum to make it greater than the single element.

The Kadane algorithm is able to pin point the subsequence of interest without generating a complete enumeration of all the contiguous subsequences.

The kadane algorithm is able to find this maximum sum with 1 pass on the array (O(n) in big O notation). My brute force implementation generating the subsequences and summing them is on the order of O(n^2) maybe a little less.

The previous local maximums need to be saved then at each element a decision can be made to continue summing or to start a new possible sum with the current element. Henry Rich's J for C programmers is a store house of J programming idioms. It is available online here: https://www.jsoftware.com/help/jforc/contents.htm

Henry Rich's Chapter 25. Loopless Code VI (https://www.jsoftware.com/help/jforc/loopless_code_vi_temporary_v.htm#_Toc191734469) shows how to use a global variable for these purposes. In J this variable can be set to minus infinity and will be lower than any element that would begin the array. Therefore it will be replaced on the first step of the algorithm. The test case is small it was easy to step through the process by hand as shown below:

NB. call the global 'locmax' for local maximum.

locmax =: __

myvec
_2 1 _3 4 _1 2 1 _5 4

NB. add the current element to locmax (this is the current candidate partial sum)
NB. pick the higher of the sum or the current element to be the next locmax.

]locmax =: _2 >. _2 + locmax   NB. processing first element
_2
]locmax =: 1 >. 1 + locmax   NB. processing second element, sum rest to element since it is higher than sum
1
]locmax =: _3 >. _3 + locmax   NB. processing third element
_2
]locmax =: 4 >. 4 + locmax   NB. processing fourth element
4
]locmax =: _1 >. _1 + locmax   NB. processing fifth element
3
]locmax =: 2 >. 2 + locmax   NB. processing sixth element
5
]locmax =: 1 >. 1 + locmax   NB. processing seventh element
6
]locmax =: _5 >. _5 + locmax   NB. processing eighth element
1
]locmax =: 4 >. 4 + locmax   NB. processing ninth element
5

NB. scanning the answers 6 is the largest sum of a subsequence
NB. the same answer as our naive brute force approach.

NB. if I define a Kadane function
kadane =: 3 : 'locmax =: y >. locmax + y'

NB. Use the prefix operator \ to step that function through each element
NB. the 1 is part of the prefix operator telling it to go one element at a time
locmax =: __
_2
1
_2
4
3
5
6
1
5

NB. the '\' just automates what I peformed manually above
NB. the only thing left is to pick out the maximum from this answer
locmax =: __
6

NB. if you look at the code for 'kadane' a fork becomes apparent
kadane1 =: 3 : 'locmax =: (] >. locmax&+) y'

NB. it indeed works the same way as the first kadane
locmax =: __
6

NB. We can use the new function definition in J to use an anonymous function
NB. for this
locmax =: __
>./ 1 {{locmax =: (] >. locmax&+) y}}\myvec
6

NB. This now has the similar structure to Conor's attempt in APL.

NB. But wait there's more
NB. Henry's book was written before 'Fold' was added to J
NB. I forget at times that Fold is in the language. As I
NB. was editing this document it dawned on me Henry Rich's idiom is a Fold.
NB. Fold will traverse the Array applying the previous calculated value
NB. into the next calculation in the chain
__ ] F:. ([ >. +) myvec
_2 1 _2 4 3 5 6 1 5          NB. this is the intermediate answer to Kadane

NB. now just apply the maximum reduce '>./' to the list
>./ __ ] F:. ([ >. +) myvec
6

## Further Discussion

An interesting side note. The fork used in the fold is essentially Conor Hoekstra's fork in APL with a slight difference. The Fold implementation in J takes the y argument (which is the right argument of the dyadic Fold) and uses it as the left argument internally to the fold implementation.

In Conor's APL he uses the '⊢' operator (same/right operator) which has the J equivalent ']'. This is taking the current right hand element and using it as an operand into the maximum operator.

The Fold in J will set up the fork as

(myvec [ __) >. (myvec + __)   NB. pseudo code of the first Fold step

Hence the use of the same/left operator '[' in the final J implementation

## programming@jsoftware.com - J programming mailing list

I had some questions about the memory usage of some of the methods for the maximal sum of the subsequences (brute force and kadane). I posted to the jsoftware programming mailing list.

Elijah Stone

Elijah gave me a simple change to the use of 'kadane'. It turns out that by using the J advanced feature of verb rank, we can direct the 'kadane' verb to work over individual elements without the use of the '\' scan adverb. Verbs can be directed to work over the different ranks of a noun: for example individual cells or applied to individual rows in a table. I won't go into an in-depth treatment of rank here. the double quote '"' is the operator that gets tacked on to the verb name and specifies the rank the verb should use. Elijah also used the display left operator/verb to turn this into a 1 liner. Remember J interprets from right to left, so below locmax will get initialized first and '[' will display the result from the left hand portion.

]myvec =: _2 1 _3 4 _1 2 1 _5 4
_2 1 _3 4 _1 2 1 _5 4

>./ kadane"0 myvec [ locmax=: __
6

This is pretty good improvement. We drop one operator for another and save some memory space.

Jose Mario Quintana

The memory usage became secondary when Jose Mario Quintana posted the following pearl:

6

Raul Miller, Henry Rich and Jose Mario Quintana
The rest of the thread on the mailing list were these 3 trying to get it through my thick skull that this indeed was a full Kadane Algorithm that operates on each value in the array only once. Producing a linear time algorithm. The best part of J and the most frustrating, is that you dance around an elegant form of an algorithm (such as 'kad'). Yet, it's elusive, then someone points it out and you think of course! Like the arrow in the FedEx logo you can't unsee it. Half the fun of programming in J are these enlightening moments where you understand an elegant piece of code.

I won't go in depth on how the 'kad' algorithm works, other than to say does it indeed accomplish this in linear time. When the reduce operator '/' is used in conjunction with the suffix operator '\.' the J interpreter recognizes this as a special case. Raul Miller pointed out you need to know where to look in the documentation:

This lists the J idioms that take advantage of specialized processing through the use of "virtual nouns". The take away being (as complex as virtual nouns sound) it speeds up processing in a number of J related situations.

## Timings

The following are time and space calculations for the various versions of this problem. Timings were accomplished on 2019 era MacBook Pro with 2.3 GHz Intel I9 8-core processor. The version of J is the latest 9.4 release for MacOs.

The routines have been reproduced here so this is self contained and you won't have to refer back to the text of this essay to understand what is being tested.

timespacex
6!:2 , 7!:2@]

ranvec =: _5 + ?10000\$10
kadane =: 3 : 'locmax =: y >. locmax + y'
kadane1 =: 3 : 'locmax =: (] >. locmax&+) y'

timespacex '>./(>./@(+/\))\.ranvec'                              NB. first brute force implementation
0.032948 396448
timespacex '>./([: >./ (+/\))\. ranvec'                          NB. fork version brute force
0.034208 396448
locmax =: __
0.004034 1.41251e6
locmax =: __
0.005267 1.41277e6
locmax =: __
timespacex '>./ 1 {{locmax =: y >. locmax + y}}\ranvec'         NB. new dnfs anonymous kadane function
0.003625 1.41347e6
locmax =: __
timespacex '>./ 1 {{locmax =: (] >. locmax&+) y}}\ranvec'       NB. fork dnfs anonymous kadane function
0.004776 1.41386e6
timespacex '>./ __ ] F:. ([ >. +) ranvec'                        NB. Fold kadane implementation
0.017393 905792
timespacex '<./ kadane"0 ranvec' [ locmax=:__                  NB. kadane with rank 0 processing
0.003909 772960