4
$\begingroup$

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

Improve this question
$\endgroup$
9
  • 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, 2022 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$
    – Marzio De Biasi
    Jan 10, 2022 at 9:10
  • $\begingroup$ Ok fair enough, thanks. $\endgroup$
    – holf
    Jan 10, 2022 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, 2022 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, 2022 at 22:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.