Message Boards Message Boards

1
|
5958 Views
|
11 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Functional programming question ...

I was recently challenged with the following puzzle ...

Find the maximum subsequence sum of a list of integers.

Here's a list ...(1, 2, -4, 1, 3, -2, 3, -1).

The maximum subsequence sum is 5 = 1+3-2+3. One does not need to remember which subsequence yields the maximum, thus ties are not important

Allegedly, the trick is to note that one can discard subsequences as soon as the sum goes down when processing linearly.

How would one do this "functionally," without generating all subsequences first?

After some years of practice I now think more about sets, and operations on them, rather than serial - procedural - operations on sequences. As this community will understand, often the set-based approach proves to be faster and more transparent.

A non-procedural solution to this puzzle is eluding me.

Thank you.

POSTED BY: Mark Tuttle
11 Replies

I found this method to be much faster than some other methods...

Does it also give the same results?

POSTED BY: Ilian Gachevski

Try this:

ClearAll[MaxSubSeq]
MaxSubSeq[x_List] := Module[{y},
  y = Accumulate[x];
  y = Ordering[x, -1][[1]];
  Max[Accumulate[Reverse[Take[x, y]]]]
  ]

the first line will calculate cumulative sum. Then we find the position of the maximum in that list. We take now only the original data up to that position we just found. We reverse the list, accumulate again, and find the max.

I found this method to be much faster than some other methods...

POSTED BY: Sander Huisman

It is a well-known problem and many approaches are available on the web, look for Kadane's algorithm.

Below is a functional style implementation, see this link for the derivation

In[1]:= data = {1, 2, -4, 1, 3, -2, 3, -1};
        f[{y_, z_}, x_] := {Max[{0, x + y}], Max[Max[0, x + y], z]}
        Last[Fold[f, {0, 0}, data]]

Out[3]= 5
POSTED BY: Ilian Gachevski

Thank you, Ilian! I suspected it had been studied.

I really appreciate the "functional" implementation - a good example of how to serialize something in Mathematica.

I'll now declare this thread CLOSED. I appreciate everyone's help.

POSTED BY: Mark Tuttle
Posted 10 years ago

It is difficult to think of a solution that does not over-enumerate, except perhaps that no subsequence that begins with a negative number can be a candidate. So here is an exhaustive approach, which could be made much less understandable by more creative coding. ;-)

In[1]:= data = {1, 2, -4, 1, 3, -2, 3, -1};

In[2]:= (* start and end of all possible subsequences *)
indices = 
 Flatten[Table[{i, j}, {i, Length[data]}, {j, i, Length[data]}], 1]

Out[2]= {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {1, 
  8}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {3, 
  3}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {4, 4}, {4, 5}, {4, 
  6}, {4, 7}, {4, 8}, {5, 5}, {5, 6}, {5, 7}, {5, 8}, {6, 6}, {6, 
  7}, {6, 8}, {7, 7}, {7, 8}, {8, 8}}

In[3]:= subsequences = Take[data, #] & /@ indices

Out[3]= {{1}, {1, 2}, {1, 2, -4}, {1, 2, -4, 1}, {1, 2, -4, 1, 3}, {1,
   2, -4, 1, 3, -2}, {1, 2, -4, 1, 3, -2, 3}, {1, 2, -4, 1, 3, -2, 
  3, -1}, {2}, {2, -4}, {2, -4, 1}, {2, -4, 1, 3}, {2, -4, 1, 
  3, -2}, {2, -4, 1, 3, -2, 3}, {2, -4, 1, 3, -2, 3, -1}, {-4}, {-4, 
  1}, {-4, 1, 3}, {-4, 1, 3, -2}, {-4, 1, 3, -2, 3}, {-4, 1, 3, -2, 
  3, -1}, {1}, {1, 3}, {1, 3, -2}, {1, 3, -2, 3}, {1, 3, -2, 
  3, -1}, {3}, {3, -2}, {3, -2, 3}, {3, -2, 3, -1}, {-2}, {-2, 
  3}, {-2, 3, -1}, {3}, {3, -1}, {-1}}

In[4]:= sums = Total /@ subsequences

Out[4]= {1, 3, -1, 0, 3, 1, 4, 3, 2, -2, -1, 2, 0, 3, 2, -4, -3, 0, \
-2, 1, 0, 1, 4, 2, 5, 4, 3, 1, 4, 3, -2, 1, 0, 3, 2, -1}

In[5]:= (* large to small *)
orderingOfSums = Ordering[sums] // Reverse

Out[5]= {25, 29, 26, 23, 7, 34, 30, 27, 14, 8, 5, 2, 35, 24, 15, 12, \
9, 32, 28, 22, 20, 6, 1, 33, 21, 18, 13, 4, 36, 11, 3, 31, 19, 10, \
17, 16}

In[6]:= (* subsequence sum pairs *)
subsequencesAndSums = {subsequences[[orderingOfSums]], 
   sums[[orderingOfSums]]} // Transpose

Out[6]= {{{1, 3, -2, 3}, 5}, {{3, -2, 3}, 4}, {{1, 3, -2, 3, -1}, 
  4}, {{1, 3}, 4}, {{1, 2, -4, 1, 3, -2, 3}, 4}, {{3}, 
  3}, {{3, -2, 3, -1}, 3}, {{3}, 3}, {{2, -4, 1, 3, -2, 3}, 
  3}, {{1, 2, -4, 1, 3, -2, 3, -1}, 3}, {{1, 2, -4, 1, 3}, 
  3}, {{1, 2}, 3}, {{3, -1}, 2}, {{1, 3, -2}, 
  2}, {{2, -4, 1, 3, -2, 3, -1}, 2}, {{2, -4, 1, 3}, 2}, {{2}, 
  2}, {{-2, 3}, 1}, {{3, -2}, 1}, {{1}, 1}, {{-4, 1, 3, -2, 3}, 
  1}, {{1, 2, -4, 1, 3, -2}, 1}, {{1}, 1}, {{-2, 3, -1}, 
  0}, {{-4, 1, 3, -2, 3, -1}, 0}, {{-4, 1, 3}, 0}, {{2, -4, 1, 3, -2},
   0}, {{1, 2, -4, 1}, 
  0}, {{-1}, -1}, {{2, -4, 1}, -1}, {{1, 
   2, -4}, -1}, {{-2}, -2}, {{-4, 1, 3, -2}, -2}, {{2, -4}, -2}, {{-4,
    1}, -3}, {{-4}, -4}}

In[7]:= max = subsequencesAndSums[[1]]

Out[7]= {{1, 3, -2, 3}, 5}
POSTED BY: David Keith

Ah, yes, that was dense of me. I will give it some more thought....

POSTED BY: David Reiss

Inspired by Gustavo's use of Partition (it works like a champ) ... here is the over-enumerated, but "functional paradigm", solution.

data={1,2,-4,1,3,-2,3,-1}; Max[Total /@ Flatten[Table[ Partition[data, i, j], {i, Length[data]}, {j, Length[data]}], 2]]

So, on this (puzzle) example, this solution (gets the right answer, 5) but it generates 121 subsequences in doing so. Using the procedural approach one need examine only a handful of subsequences though with lots of conditional statement executions. (Though I haven't, yet, formulated the worst-case for that approach.)

Still asking, is this - functional shortfall - intrinsic?

Thank you.

POSTED BY: Mark Tuttle

This runs in O(n^2) time, not very efficient, as you can do it in O(n) time...

POSTED BY: Sander Huisman

First, in response to David's question, the key aspect of the problem definition is the subsequence notion - namely that a subsequence is a consecutive list of 1 or more elements, and not just any subset (as Gustavo observes).

Second, in response to Gustavo's interesting suggestion, it's missing some cases - the maximum sum might come from a single (large positive) number, for example. Further, the point of this particular puzzle is to avoid over-enumerating.

That said, I'm completely in favor of the over-enumeration one often gets with the use of the functional programming paradigm. I'm just asking if there's a functional approach to this puzzle that doesn't over-enumerate. Or, is this puzzle inherently sequential, and thus centrally "procedural"?

POSTED BY: Mark Tuttle
Posted 10 years ago

Generating all subsequences it can be done like:

data={1,2,-4,1,3,-2,3,-1};
Last@SortBy[Flatten[Table[Partition[data,s,1],{s,2,Length[d-1]}],1],Total]

David, I infer that the numbers to consider need to be consecutive.

POSTED BY: Gustavo Delfino

What are the rules for this problem? The way I read it, the answer is simply the sum of the positive entries (which would give the answer as 1+2+1+3+3). I am guessing that this is not the interpretation that you are using in getting the answer 1+3-2+3.

POSTED BY: David Reiss
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract