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

  • 2
    $\begingroup$ 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? $\endgroup$
    – holf
    Jan 10 at 6:06
  • 1
    $\begingroup$ @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" :-) $\endgroup$ Jan 10 at 9:10
  • $\begingroup$ Ok fair enough, thanks. $\endgroup$
    – holf
    Jan 10 at 15:45
  • $\begingroup$ 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! $\endgroup$
    – Travis
    Jan 10 at 17:53
  • 2
    $\begingroup$ 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). $\endgroup$
    – Travis
    Jan 10 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.