Какой алгоритм использовать, чтобы: разбить массив чисел так, чтобы суммарная разница между максимальным и минимальным числом была максимальна?

Question

[BAF1]

У меня есть массив чисел, мне нужно разбить его на группы так, чтобы каждая из них была длины от l до r (менять порядок чисел (сортировать) нельзя) и, чтобы суммарная разница между максимальным и минимальным числом была максимальна.
Если разбиение возможно несколькими способами, то вывести любой из них

Например, есть массив [98, 99, 98, 100, 98, 99, 98]; l = 2; r = 4. В ответе будет разбиение на 3 подмассива: [98, 99] [98, 100] [98, 99, 98]. Суммарная разница здесь будет 4.

Я вот думаю, есть ли тут динамическое программирование?

Comments

[Everything_is_bad]

при чем тут python?

[BAF1]

Everything_is_bad, да, пытаюсь решить это на python вот и написал. Действительно, к вопросу это дел не имеет

[Rsa97]

А почему не [98, 99, 98, 100], [98, 99, 98]? Тогда суммарная разность будет 3.

[BAF1]

Rsa97, суммарная разность должна быть максимальна

Answer 1

[Wataru]

Ага, ДП тут отлично входит. F(n) - ответ на задачу для префикса длины n. Там перебираете длину последней группы x и берете в качесвте ответа max(a[n-x]..a[n-1]) - min(a[n-x]..a[n-1]) + F(n-x). По всем l<=x<=r выбераете максимум. Если n < l, то ответ - минус бесконечность.

Это будет решение за O(n^2). Что-нибудь за O(n log n) я так сходу придумать не могу.

Comments

[Alexandroppolus]

почему n^2 ?

базово на каждую новую n придется сделать O(r-l) итераций для поиска максимумов и минимумов
итого O(n * (r - l)), там может (r - l) сильно меньше n.

но если они таки сравнимы с n, то ещё навскидку кажется (хотя и нельзя сказать наверняка), что для вычисления max и min в очередной группе можно применить тот прием со стеком, который используется для вычисления оных на sliding window. Последняя группа смещается похожим образом. Если так, то будет вообще линейно.

[BAF1]

Спасибо, сейчас попробую

[Wataru]

Alexandroppolus,

там может (r - l) сильно меньше n.

Может. Но пока об этом ничего не сказано, оценка сверху остается O(n) на каждое f().

что для вычисления max и min в очередной группе можно применить тот прием со стеком, который используется для вычисления оных на sliding window. Последняя группа смещается похожим образом. Если так, то будет вообще линейно.

Ну не, это же только для фиксированного размера группы сработает. Если там хоть какой-то разброс есть r-l, то sliding window уже нe работает.

[Wataru]

BAF1, Попробуйте тест aaaaa 3 4
Должно быть NO SOLUTION.

А можно ли вывести всю строку, как одно слово? Вы, вроде как требуете всегда хотя бы 2 слова, но, может это и не надо? В тесте aaaaa 5 5 должно вывести одно слово aaaaa.

[BAF1]

Wataru, уже прошёл тот тест с помощью строчки sequence.length != result.first.joinToString("").length, но теперь не проходит по времени (ограничение 1 секунда, а у меня 1.087), если нужен код вот, тот удалил:

fun main() {
    Task5().run()
}

class Task5 {
    fun run() {
        val (_, l, r) = readln().split(" ").map { it.toInt() }
        val sequence = readln()

        val result = maxDifference(sequence, l, r)
        if (sequence.length != result.first.joinToString("").length) {
            println("NO SOLUTION")
            return
        }
        println(result.second)
        println(result.first.size)
        println(result.first.joinToString("\n"))
    }

    private fun maxDifference(a: String, l: Int, r: Int): Pair<List<String>, Int> {
        val n = a.length
        val words = Array(n + 1) { Pair(emptyList<String>(), 0) }

        for (i in l..n) {
            for (x in l..r) {
                if (i >= x) {
                    val slice = a.substring(i - x, i)
                    var maxChar = Int.MIN_VALUE
                    var minChar = Int.MAX_VALUE
                    for (char in slice) {
                        val code = char.code
                        if (code > maxChar) maxChar = code
                        if (code < minChar) minChar = code
                    }
                    val new = words[i - x].second + (maxChar - minChar)
                    if (words[i].second <= new) {
                        val newArr = words[i - x].first.toMutableList()
                        newArr.add(slice)
                        words[i] = Pair(newArr, new)
                    }
                }
            }
        }

        return words.last()
    }
}

[BAF1]

Wataru, да, вы были правы, одно слово может быть, исправил это строчкой if (sequence.length != result.first.joinToString("").length) {...}