G'day:
There was another Friday Puzzle on the CFML Slack channel this week. The question was:
The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:
maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
// should be 6: [4, -1, 2, 1]
Apparently the word "contiguous" is something that will flummox some people (judging by the discussion on the Slack channel). In this sense a contiguous sub-sequence is one that is made from adjacent array elements. So you can see they highlighted sub-sequence is a subset of adjacent array elements.
Eyeballing the example series here reveals the tricky bit one needs to watch for... negative values. Take a sub-sequence of 3,4. That has a sum of 7. Now if the next number is negative: 3,4,-1 (sum 6), the sum of this longer sub-sequence is
less than that of the preceding shorter one, so the shorter subsequence is still the "winner". However if the
next number (or numbers) sum to greater than the negative number, eg; 3,4,-1,2 (sum 8) then we've got the highest sum again. And of course there could be more negative numbers followed by positive numbers with a higher sum repeatedly.
A couple of the bods on the Slack channel quickly came up with solutions. Here they are, respectively:
Isaiah's and
John's. I'll only repeat one of them here because both used pretty much the same algorithm, just one used procedural code, and the other a more functional approach (in that they used higher-order functions). But they've both got the same logic error in them, because the approach is flawed. Let's have a look at John's one:
numeric function maxSequence(required array arr){
var currentSum = 0;
return arr.reduce(function(maxSum, number){
currentSum = max(currentSum+number, 0);
return max(currentSum, maxSum);
}, 0);
}
WriteDump(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
WriteDump(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4, 3]));
WriteDump(maxSequence([-2, -3, -1, -5]));
WriteDump(maxSequence([1, 4, 2, 1, 4, 3]));
This is nice and simple, and it took me a while to get what he's doing here. But we're keeping a running sum of the sequence outside the callback, and the callback itself returns the greater of the running sum or the whatever has previously been the maximum sum. So taking the first series there, we get the following iterations:
| maxSum | number | currentSum | newMax |
|---|
| 0 | -2 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | -3 | 0 | 1 |
| 1 | 4 | 4 | 4 |
| 4 | -1 | 3 | 4 |
| 4 | 2 | 5 | 5 |
| 5 | 1 | 6 | 6 |
| 6 | -5 | 1 | 6 |
| 6 | 4 | 5 | 6 |
Superficially this seems OK, except for one thing: it considers the minimum possible sum to be
0. Which is not correct. In a sequence with only negative numbers... the maximum sum will be the highest negative number: in
[-1,-2,-3] the highest sum there is
-1, but sums less than zero are ignored by this algorithm, so it incorrectly returns
0. Equally for an empty sequence, the answer is
null or
undefined, so this algorithm will fail there too, as it returns
0 for this too (as it defaults to a maximum sum of zero, whereas we don't know there'll be a sum when we start the process. So I guess that's two slightly different logic errors there.
I'll come back to John's solution in a bit, but first here's my solution. It's not as elegant as John's, and I'm not entirely happy with it, but it does work.
Here's the code (I've opted to do mine in ES2015 rather than CFML):
let sumLongestContiguousSubsequence = function (array) {
let subSequences = array.map((_,i,a)=>a.slice(i));
return subSequences.reduce(function(max, subsequence){
let runningSum = subsequence[0];
let maximumSubSequenceSum = subsequence.reduce(function(max, element){
return (runningSum += element) > max ? runningSum : max;
});
return Math.max(max||maximumSubSequenceSum, maximumSubSequenceSum);
}, null);
};
My conceit is that one cannot make assumptions about any earlier maximums, so
I don't default the answer to anything.
Also
I don't default the running sum to anything, I just take its starting point as the first element of the sequence I'm checking.
The general approach here is slightly more ham-fisted than John's approach.
- I figure I need to scan each separate sub-sequence of the main sequence, starting each sub-sequence from each subsequent value in the main sequence. EG: if I have a sequence of [1,2,3,4], then
subSequences will be [[1,2,3,4],[2,3,4] [3,4],[4]].
- For each of those I do much the same thing as John: just run a cumulative sum, and remember whatever the highest value for that was.
- So that'll bring me back to an array of maximums (in my [1,2,3,4] example, this'd be [10,9,7,4].
- And as I reduce that lot, I simply return whichever is the higher of the previous ones and the current one.
I also wrote actual tests here. And this is where my approach differs from John's (or Isaiah's for that matter). When I test things I don't try to demonstrate to myself it works, I try to break the thing.
Here are my tests:
"use strict";
let assert = require("chai").assert;
let sumLongestContiguousSubsequence = require("./sumLongestContiguousSubsequence.js");
describe("Test of puzzle requirement", function(){
it("returns the highest contiguous subseries sum for baseline requirement", function(){
let sequence = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
let expectation = 4 + -1 + 2 + 1; // 6
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
});
describe("Tests of other puzzle submission sequences", function(){
it("returns the highest contiguous subseries sum for variation 1", function(){
let sequence = [-2, 1, -3, 4, -1, 2, 1, -5, 4, 3];
let expectation = 4 + -1 + 2 + 1 + -5 + 4 + 3; // 8
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
it("returns the highest contiguous subseries sum for variation 2", function(){
let sequence = [-2, -1, -3, -5];
let expectation = -1;
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
it("returns the highest contiguous subseries sum for variation 3", function(){
let sequence = [1, 4, 2, 1, 4, 3];
let expectation = 1 + 4 + 2 + 1 + 4 + 3; // 15
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
});
describe("Test edge cases", function(){
it("returns the highest contiguous subseries sum with an empty array", function(){
let sequence = [];
let expectation = null;
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
it("returns the highest contiguous subseries sum with just zero", function(){
let sequence = [0];
let expectation = 0;
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
it("returns the highest contiguous subseries sum with just -1", function(){
let sequence = [-1];
let expectation = -1;
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
it("returns the highest contiguous subseries sum with just 1", function(){
let sequence = [1];
let expectation = 1;
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
});
describe("Better described tests", function(){
it("returns the highest contiguous subseries sum when the sequence has negative values", function(){
let sequence = [1,2,3,-11];
let expectation = 1 + 2 + 3; // 6
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
it("returns the highest contiguous subseries sum when the sequence has negative values followed by a greater positive value", function(){
let sequence = [1,2,3,-4,5];
let expectation = 1 + 2 + 3 + -4 + 5; // 7
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
it("returns the highest contiguous subseries sum when the sequence has negative values followed by a subseries positive values that are net greater than the negative one", function(){
let sequence = [2,4,6,-8,3,7];
let expectation = 2 + 4 + 6 + -8 + 3 + 7; // 14
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
it("returns the highest contiguous subseries sum when the sequence has repeated negative values followed by a subseries positive values that are net greater than the negative one", function(){
let sequence = [12,14,16,-8,3,7,-12,5,9];
let expectation = 12 + 14 + 16 + -8 + 3 +7 + -12 + 5 + 9; // 46
let result = sumLongestContiguousSubsequence(sequence);
assert.equal(expectation, result);
});
});
These are fairly deliberate in what they test, but don't try to do anything clever (so there's a lot of repeated code). I make a point of testing edge cases like empty sequences, and sequences with only one element, and all negative values and all positive values etc. My philosophy with testing is that I'm not trying to demonstrate the code works, I'm trying to demonstrate it doesn't break. This amounts to the same thing, but it starts from a slightly different mindset. Testing is one situation where "glass half empty" rather than "glass half full" is the better way to look at things.
So this version of the solution works, but I'm not happy about it. For one thing, I don't think one can look at it and go "right, it's clear what's going on there". I looked for refactoring opportunities, but am not seeing any. Maybe
subSequences could have a better name? I looked at extracting the callbacks into named function expressions, but that didn't look any clearer to me either.
let sumLongestContiguousSubsequence = function (array) {
let runningSum;
let getCurrentMaxSum = function(max, element){
return (runningSum += element) > max ? runningSum : max;
};
let findSumOfLongestSub = function(max, subsequence){
runningSum = subsequence[0];
let maximumSubSequenceSum = subsequence.reduce(getCurrentMaxSum);
return Math.max(max||maximumSubSequenceSum, maximumSubSequenceSum);
};
let subSequencesSlicedAtEachIndex = array.map((_,i,a)=>a.slice(i));
return subSequencesSlicedAtEachIndex.reduce(findSumOfLongestSub, null);
};
What do you think: is that clearer? I guess it's a
bit better, innit? It's straying away from "elegance in simplicity" though.
Ha, just for a laugh I took the code clarity in the opposite direction. How about this mess:
let f=a=>a.map((_,i,a)=>a.slice(i)).reduce((m1,s)=>{
let t=s[0],m2=s.reduce((m,v)=>(t+=v)>m?t:m)
return Math.max(m1||m2,m2)
},null)
It's the same
logic as my original version.
The other issue that Sean and Ryan are likely to pull me up on is that one of my reductions relies on
side-effects spilling out into the intermediary calling code:
let sumLongestContiguousSubsequence = function (array) {
let subSequences = array.map((_,i,a)=>a.slice(i));
return subSequences.reduce(function(max, subsequence){
let runningSum = subsequence[0];
let maximumSubSequenceSum = subsequence.reduce(function(max, element){
return (runningSum += element) > max ? runningSum : max;
});
return Math.max(max||maximumSubSequenceSum, maximumSubSequenceSum);
}, null);
};
This didn't actually bother me until I did the PHP version of this, where the side-effects are more glaring:
$sumLongestContiguousSubsequence = function ($array) {
$subSequences = array_map(function($i) use ($array) {
return array_slice($array, $i);
}, array_keys($array));
return array_reduce($subSequences, function($max, $subSequence){
$runningSum = 0;
$maximumSubSequenceSum = array_reduce($subSequence, function($max, $element) use (&$runningSum){
return ($runningSum += $element) > $max ? $runningSum : $max;
}, $subSequence[0]);
return max($max?:$maximumSubSequenceSum, $maximumSubSequenceSum);
}, null);
};
PHP sux a bit because it doesn't do closure implicitly,
one needs to tell it what to enclose, which is clumsy IMO. But it's also a bit of an orange flag. This orange flag becomes a red flag when I need to actually use
a reference here, cos I'm changing the original value, not simply using it.
That guilt-tripped me into revising my JS version so as to not need the side effects:
let sumLongestContiguousSubsequence = function (array) {
let subSequences = array.map((_,i,a)=>a.slice(i));
return subSequences.reduce(function(max, subsequence){
let maximumSubSequence = subsequence.reduce(function(working, element){
working.runningSum += element;
working.max = working.max || working.runningSum;
working.max = working.runningSum > working.max ? working.runningSum : working.max
return {max:working.max, runningSum:working.runningSum};
}, {runningSum:0});
return Math.max(max||maximumSubSequence.max, maximumSubSequence.max);
}, null);
};
Now I'm
carrying both the runningSum and the max value through the first argument in the reduction, by using an object rather than just the simple value. It's a small change but gets rid of the smell. To be completely honest though... I prefer my original version. I realise it's frowned-upon to bleed side-effects (which I then leverage), but this refactoring seems like an exercise in pedantic/dogmatic busy-work, and makes the code slightly less clear in the process. I dunno.
Oh, for completeness I did a CFML conversion too:
sumLongestContiguousSubsequence = function (array) {
var subSequences = array.map((_,i,a) => a.slice(i));
return subSequences.reduce(function(maxSum, subSequence){
var runningSum = 0;
var maximumSubSequenceSum = subSequence.reduce(
(maxSum, element) => (runningSum += element) > maxSum ? runningSum : maxSum,
subSequence[1]
);
return max(maxSum ?: maximumSubSequenceSum, maximumSubSequenceSum);
}, null);
};
Note that this solution only works on Lucee, not ColdFusion, for three reasons:
- ColdFusion does not have arrow functions;
- ColdFusion has a bug in its parser which breaks on this expression (see 4190163);
- Lucee has a null keyword whereas ColdFusion does not.
The Lucee version is OK though. Same as the JS version for the most part: just 1-based arrays, not 0-based; and Lucee has the
?: operator whereas JS uses
||.
That's about all I can think to say about this. I might see if I can mess with John's approach to make it work for those two edge-cases it fails on. I much prefer his way compared to my way... but only provided it can be made to work! I'd also be keen to see treatments of this puzzle in other languages, or better/different solutions for JS, PHP or CFML.
Righto.
--
Adam
