# Split a string of positive numbers into substrings with decreasing totals

Suppose we're given a string of $$n$$ positive numbers and asked to split it into the maximum number of substrings whose totals are decreasing. I have an $$O(n)$$ time DP algorithm, but is it already known? I can find lots of pages about splitting the numbers into the maximum number of subsets (or, more precisely, sub-multisets) with decreasing sums --- to build a pyramid, for example --- but I don't want to rearrange the numbers.

For example, given $$6, 2, 4, 3, 2, 2, 5$$, we can split it into $$6, 2, 4$$ (total $$12$$) and $$3, 2, 2$$ (total $$7 < 12$$) and $$5$$ (total $$5 < 7$$).

This started as an open problem at CCCG '21. Here's a detailed presentation: https://arxiv.org/abs/2109.14497 .

Thanks, Travis

• I am a bit puzzled by the downvote. Sure, the problem does not seem "research level" but it is a "reference request" kind of question: the OP wants to know whether this problem has a name and is already studied in literature. Am I missing something?
– holf
Jan 10 at 6:06
• @holf Probably because the problem looks more like an exercise, and the reference request is not for research purposes. I think that the downvotes simply mean "this question should not be here" :-) Jan 10 at 9:10
• Ok fair enough, thanks.
– holf
Jan 10 at 15:45
• I realized after I posted it that it might sound like someone's homework question. I posted to arxiv a few months ago a linear solution (arxiv.org/abs/2109.14497) to an open problem posed at CCCG '21, which I now think is pretty much equivalent to this one. I can't believe no one has studied this one before, but I can't find a reference. Thanks again! Jan 10 at 17:53
• The question at CCCG was to partition the strings of numbers into substrings with decreasing totals such that the largest total is minimized (originally phrased in terms of wrapping a carpenter's ruler). We designed a linear-time algorithm to solve that, and then found it also maximizes the number of substrings (the proof should show up in an arxiv update tomorrow). Jan 10 at 22:28