<p>Suppose we're given a string of <span class="math-container">$n$</span> positive numbers and asked to split it into the maximum number of substrings whose totals are decreasing.  I have an <span class="math-container">$O(n)$</span> 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.</p>
<p>For example, given <span class="math-container">$6, 2, 4, 3, 2, 2, 5$</span>, we can split it into <span class="math-container">$6, 2, 4$</span> (total <span class="math-container">$12$</span>) and <span class="math-container">$3, 2, 2$</span> (total <span class="math-container">$7 &lt; 12$</span>) and <span class="math-container">$5$</span> (total <span class="math-container">$5 &lt; 7$</span>).</p>
<p>This started as an open problem at CCCG '21.  Here's a detailed presentation: <a href="https://arxiv.org/abs/2109.14497" rel="nofollow noreferrer">https://arxiv.org/abs/2109.14497</a> .</p>
<p>Thanks,
Travis</p>

CC BY-SA 4.0
2022-01-10T06:06:00.307Z
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
CC BY-SA 4.0
2022-01-10T09:10:42.873Z
@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" :-)
Marzio De Biasi
CC BY-SA 4.0
2022-01-10T15:45:15.353Z
Ok fair enough, thanks.
holf
CC BY-SA 4.0
2022-01-10T17:53:18.247Z
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 (https://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!
Travis
CC BY-SA 4.0
2022-01-10T19:46:06.217Z
@Travis in this case it seems ok to ask for references on cstheory ... you should also clarify if it is the same (open/solved) problem posed at CCCG21 and if not explain the differences (in your comment you say "pretty much equivalent")
Marzio De Biasi
CC BY-SA 4.0
2022-01-10T22:28:24.327Z
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).
Travis
CC BY-SA 4.0
2022-01-12T18:01:38.130Z
Am I missing something? It looks like this problem can be solved by a trivial greedy algorithm, traversing the string in reverse order. Starting from the end, you want each substring to be as small as possible, provided its total is enough to be larger than the next substring. The last substring will always have length 1, so in your example it is [5]. The second-to-last substring is the smallest substring with total higher than 5: it's not [2], it's not [2,2], so it's [3,2,2]. Etc.
Stef
CC BY-SA 4.0
2022-01-12T22:21:57.300Z
Why would the last substring be of length $1$? Solving the problem on input [1,2] leaves you no choice to take 1 and 2 together.
holf
CC BY-SA 4.0
2022-01-13T23:39:51.107Z
I thought I posted this yesterday... There's a proof in the paper that the greedy algorithm has an approximation ratio in Omega(sqrt(n)).  Consider 2, 1, 3.001, 3.002, 2.003, 1.004, 3.005, 3.006, 3.007, 3.008, 2.009, 1.01, ... --- with "2, 1" pairs separated by two 3s, then by four 3s, then by six 3s, etc.  The greedy algorithm splits it 2 | 1, 3.001 | 3.002, 2.003 | 1.004, 3.005, 3.006 | 3.007, 3.008, 2.009 | 1.010, ..., while it can be split 2, 1 | 3.001 | 3.002 | 2.003, 1.004 | 3.005 | 3.006 | 3.007 | 3.008 | 2.009, 1.01, ... .
Travis
<reference-request><partition-problem><dynamic-programming>
Split a string of positive numbers into substrings with decreasing totals
Travis
# Split a string of positive numbers into substrings with decreasing totals

(Asked by: username_0 on 2022-01-09)

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

**Tags:** reference-request, partition-problem, dynamic-programming
> **Comments:**
> **username_1**: 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?  
> **username_2**: @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" :-)  
> **username_1**: Ok fair enough, thanks.  
> **username_0**: 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 (https://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!  
> **username_2**: @Travis in this case it seems ok to ask for references on cstheory ... you should also clarify if it is the same (open/solved) problem posed at CCCG21 and if not explain the differences (in your comment you say "pretty much equivalent")  
> **username_0**: 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).  
> **username_3**: Am I missing something? It looks like this problem can be solved by a trivial greedy algorithm, traversing the string in reverse order. Starting from the end, you want each substring to be as small as possible, provided its total is enough to be larger than the next substring. The last substring will always have length 1, so in your example it is [5]. The second-to-last substring is the smallest substring with total higher than 5: it's not [2], it's not [2,2], so it's [3,2,2]. Etc.  
> **username_1**: Why would the last substring be of length $1$? Solving the problem on input [1,2] leaves you no choice to take 1 and 2 together.  
> **username_0**: I thought I posted this yesterday... There's a proof in the paper that the greedy algorithm has an approximation ratio in Omega(sqrt(n)).  Consider 2, 1, 3.001, 3.002, 2.003, 1.004, 3.005, 3.006, 3.007, 3.008, 2.009, 1.01, ... --- with "2, 1" pairs separated by two 3s, then by four 3s, then by six 3s, etc.  The greedy algorithm splits it 2 | 1, 3.001 | 3.002, 2.003 | 1.004, 3.005, 3.006 | 3.007, 3.008, 2.009 | 1.010, ..., while it can be split 2, 1 | 3.001 | 3.002 | 2.003, 1.004 | 3.005 | 3.006 | 3.007 | 3.008 | 2.009, 1.01, ... .  

---

## 0 answers

