Наибольшая сумма из абсолютных разностей N элементов в массиве - PullRequest
Новая
       65

Наибольшая сумма из абсолютных разностей N элементов в массиве

1 голос
/ 08 ноября 2019

Это на самом деле не домашняя работа, а скорее практика и оптимизация, но это казалось лучшим разделом для вопросов такого типа.

Это проблема динамического программирования, и она следующая:

-Дать массив unsorted из N элементов, выбрать из него число элементов K, чтобы их абсолютная разница была наибольшей.

Абсолютная разница вычисляется между соседнимиэлементы здесь. Поэтому, если у нас есть массив из 5 элементов: 1 5 3 2 1 и k = 3, абсолютные различия будут:

1 5 3 = | 5-1 |+ | 3-5 |= 6

1 5 2 = | 5-1 |+ | 2-5 |= 7

1 5 1 = [5-1 |+ | 1-5 |= 8

и т. Д.

С 1 5 1, являющимся самым большим и необходимым с 8

То, что я пробовал до сих пор, - это решить эту проблему путем нахождения всех возможных комбинаций Kчисла с рекурсией и последующим возвратом наибольшего (грубая сила).

Это показалось ужасной идеей, потому что при попытке с массивом N = 50 и k = 25, например, 1,264106064E + 14комбинации.

Рекурсия, которую я использовал, является простой, используемой для печати всех K-значных целых чисел из массива, вместо того, чтобы печатать их, сохраняя их в массиве: 

static void solve(int[] numbers, int k, int startPosition, int[] result) {
        if (k == 0) {
            System.out.println(absoluteDifferenceSum(result));
            return;
        }
        for (int i = startPosition; i <= numbers.length - k; i++) {
            result[result.length - k] = numbers[i];
            solve(numbers, k - 1, i + 1, result);
        }
    }

ЧтоЯ хочу достичь оптимальной сложности (которая, я полагаю, не может быть ниже O (n ^ 2) здесь, но у меня нет идей, и я не знаю, как начать. Любая помощь приветствуется!

1 Ответ

1 голос
/ 10 ноября 2019

Как правило, у нас может быть наивная O(n^2 * k) формулировка, где f(i, k) представляет наилучший результат для выбора k элементов, когда i-й элемент является самым правым в выборе, 

f(i, k) = max(
  f(j, k - 1) + abs(Ai - Aj)
)
for all j < i

который мы можем расширить до 

  max( f(j, k - 1) + Ai - Aj )
= Ai + max(f(j, k - 1) - Aj)

when Ai >= Aj

и 

  max( f(j, k - 1) + Aj - Ai )
= -Ai + max(f(j, k - 1) + Aj)

when Ai < Aj

Поскольку правильное слагаемое не зависит от Ai, мы можем построить дерево с узлами, в которых хранятся оба f(j, k - 1) - Aj,а также f(j, k - 1) + Aj. Кроме того, мы будем хранить в каждом узле оба максимума для каждого поддерева. Нам понадобятся O(k) деревьев. Давайте перейдем к рассмотрению дерева для k = 2, когда мы достигнем последнего элемента: 

1

5 -> 4 -> (-1, 9)

3 -> 2 -> (-1, 5)

2 -> 3 -> (-1, 5)

3 -> (-3, 5)

tree for k = 2 so far:

   3 (-1, 5)
  /         \
2 (-1, 5)   5 (-1, 9)

1 is less than 3 so we first add -1
to the max for the right subtree
stored for f(j, k - 1) + Aj

-1 + 9 = 8
(note that this represents {1,5,1})

then we continue left in the tree
and compare 8 to a similar calculation
with node 2: -1 + 5 = 4
(note that this represents {5,2,1})

Таким образом, мы можем уменьшить сложность времени до O(n log n * k) с пробелом O(n * k).

...