Подтвердить что ты не робот

Максимизация определенной суммы по всем возможным подмассивам

Рассмотрим массив, подобный приведенному ниже:

  {1, 5, 3, 5, 4, 1}

Когда мы выбираем подмассив, мы сводим его к наименьшему числу в подмассиве. Например, подрамник {5, 3, 5} становится {3, 3, 3}. Теперь сумма подматрицы определяется как сумма результирующего подмассива. Например, {5, 3, 5} сумма 3 + 3 + 3 = 9. Задача состоит в том, чтобы найти максимально возможную сумму, которая может быть сделана из любого подмассива. Для вышеупомянутого массива наибольшая сумма равна 12, заданной подмассивом {5, 3, 5, 4}.

Возможно ли решить эту проблему во времени лучше, чем O (n 2)?

4b9b3361

ОТВЕТЫ

Ответ 1

Я считаю, что у меня есть алгоритм для этого, который выполняется в O (n) времени. Сначала я опишу неоптимизированную версию алгоритма, а затем даю полностью оптимизированную версию.

Для простоты пусть сначала предположим, что все значения в исходном массиве различны. Это вообще не так, но это дает хорошую отправную точку.

Основное наблюдение за алгоритмом заключается в следующем. Найдите наименьший элемент в массиве, затем разделите массив на три части - все элементы слева от минимума, сам минимальный элемент и все элементы справа от минимума. Схематически это выглядело бы как

 +-----------------------+-----+-----------------------+
 |     left values       | min |      right values     |
 +-----------------------+-----+-----------------------+

Здесь ключевое наблюдение: если вы берете подмассив, который дает оптимальное значение, одна из трех вещей должна быть правдой:

  • Этот массив состоит из всех значений в массиве, включая минимальное значение. Это имеет общее значение min * n, где n - количество элементов.
  • Этот массив не включает минимальный элемент. В этом случае подматрица должна быть чисто слева или справа от минимального значения и не может включать в себя минимальное значение.

Это дает хороший начальный рекурсивный алгоритм для решения этой проблемы:

  • Если последовательность пуста, ответ равен 0.
  • Если последовательность непусто:
    • Найдите минимальное значение в последовательности.
    • Возврат максимального значения:
      • Лучший ответ для подмассива слева от минимума.
      • Лучший ответ для субарара справа от минимума.
      • Число элементов раз минимально.

Итак, насколько эффективен этот алгоритм? Ну, это действительно зависит от того, где минимальные элементы. Если вы думаете об этом, мы выполняем линейную работу, чтобы найти минимум, а затем разделим проблему на две подзадачи и повторим каждую. Это то же самое повторение, которое вы получаете при рассмотрении quicksort. Это означает, что в лучшем случае это займет время & theta; (n log n) (если у нас всегда есть минимальный элемент в середине каждой половины), но в худшем случае это займет & Theta; (n 2) (если мы всегда имеем минимальное значение только в крайнем левом или правом углу.

Обратите внимание, однако, что все усилия, которые мы тратим, используются для нахождения минимального значения в каждом из подмассивов, который принимает O (k) время для k элементов. Что, если бы мы могли ускорить это до O (1) раз? В этом случае наш алгоритм будет делать гораздо меньше работы. В частности, это будет делать только O (n). Причиной этого является следующее: каждый раз, когда мы делаем рекурсивный вызов, мы выполняем O (1), чтобы найти минимальный элемент, затем удалим этот элемент из массива и рекурсивно обработаем оставшиеся части. Таким образом, каждый элемент может быть минимальным элементом не более одного из рекурсивных вызовов, поэтому общее количество рекурсивных вызовов не может быть больше числа элементов. Это означает, что мы делаем не более O (n) вызовов, каждый из которых выполняет O (1), что дает общее число операций O (1).

Итак, как именно мы получаем это волшебное ускорение? Здесь мы используем удивительно универсальную и недооцененную структуру данных, которая называется декартовым деревом. Декартово дерево представляет собой двоичное дерево, созданное из последовательности элементов, которая имеет следующие свойства:

  • Каждый node меньше своих детей, а
  • Проход по декартовому дереву по порядку возвращает элементы последовательности в том порядке, в котором они появляются.

Например, последовательность 4 6 7 1 5 0 2 8 3 имеет это декартово дерево:

       0
      / \
     1   2
    / \   \
   4   5   3
    \     /
     6   8
      \
       7

И здесь, где мы получаем магию. Мы можем сразу найти минимальный элемент последовательности, просто взглянув на корень декартового дерева - это занимает только время O (1). Когда мы это сделаем, когда мы делаем наши рекурсивные вызовы и просматриваем все элементы слева или справа от элемента минимума, мы просто рекурсивно спускаемся в левое и правое поддеревья корня node, что означает, что мы можем считывать минимальные элементы этих подмассивов в O (1) раз каждый. Острота!

Настоящая красота заключается в том, что можно построить декартово дерево для последовательности из n элементов в O (n) времени. Этот алгоритм подробно описан в этом разделе статьи Википедии. Это означает, что мы можем получить супер быстрый алгоритм для решения вашей исходной задачи следующим образом:

  • Построить декартово дерево для массива.
  • Используйте вышеуказанный рекурсивный алгоритм, но используйте декартово дерево для поиска минимального элемента, а не для линейного сканирования каждый раз.

В целом, это время O (n) и использует O (n) пространство, что является улучшением времени по сравнению с ранее установленным алгоритмом O (n 2).

В начале этого обсуждения я сделал предположение, что все элементы массива различны, но это действительно не нужно. Вы все равно можете построить декартово дерево для массива с неявными элементами в нем, изменив требование, чтобы каждый node был меньше, чем его дети, чтобы каждый node не был больше, чем его дети. Это не влияет на правильность алгоритма или его время выполнения; Я оставлю это как пресловутое "упражнение для читателя".: -)

Это была крутая проблема! Надеюсь, это поможет!

Ответ 2

Предполагая, что числа все неотрицательны, разве это не проблема "максимизировать прямоугольник в гистограмме"? который теперь стал известным...

O (n) возможны. Этот сайт: http://blog.csdn.net/arbuckle/article/details/710988 имеет кучу опрятных решений.

Чтобы разработать то, что я думаю (это может быть неверно), подумайте о каждом числе как прямоугольник гистограммы шириной 1.

Посредством "минимизации" подмассива [i, j] и сложения вверх вы в основном получаете площадь прямоугольника в гистограмме, которая охватывает от я до j.

Это появилось раньше на SO: Разверните прямоугольную область под гистограммой, вы найдете код и объяснение, а также ссылку на страницу официальных решений (http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html).

Ответ 3

Следующий алгоритм, который я попробовал, будет иметь порядок алгоритма, который изначально используется для сортировки массива. Например, если исходный массив сортируется по двоичному дереву, он будет иметь O (n) в лучшем случае и O (n log n) в качестве среднего случая.

Суть алгоритма:

Массив сортируется. Сохраняются отсортированные значения и соответствующие старые индексы. Двоичное дерево поиска создается из соответствующих старых индексов, которые используются для определения того, как далеко он может двигаться вперед и назад, не сталкиваясь с значением, меньшим, чем текущее значение, что приведет к максимально возможному вспомогательному массиву,

Я объясню метод с массивом в вопросе [1, 5, 3, 5, 4, 1]

                      1  5  3  5  4  1
                  -------------------------
 array indices =>     0  1  2  3  4  5  
                  -------------------------

Этот массив отсортирован. Сохраните значение и их индексы в порядке возрастания, что будет следующим:

                                   1  1  3  4  5  5
                                 -------------------------
 original array indices =>         0  5  2  4  1  3  
 (referred as old_index)         -------------------------

Важно иметь ссылку как на значение, так и на их старые индексы; как ассоциативный массив;

Несколько понятий:

old_index ссылается на соответствующий исходный индекс элемента (то есть индекс в исходном массиве);

Например, для элемента 4 old_index равен 4; current_index равно 3;

тогда как current_index относится к индексу элемента в отсортированном массиве; current_array_value ссылается на текущее значение элемента в отсортированном массиве.

pre относится к предшественнику порядка; succ относится к преемнику inorder

Кроме того, минимальные и максимальные значения могут быть получены непосредственно из первого и последнего элементов отсортированного массива, которые являются min_value и max_value соответственно;

Теперь алгоритм выглядит следующим образом, который должен выполняться на отсортированном массиве.

Алгоритм:

Перейдите от самого левого элемента.

Для каждого элемента слева от отсортированного массива примените этот алгоритм

    if(element == min_value){

    max_sum = element * array_length;

        if(max_sum > current_max)
        current_max = max_sum;

        push current index into the BST;

    }else if(element == max_value){

        //here current index is the index in the sorted array
        max_sum = element * (array_length - current_index);

        if(max_sum > current_max)
        current_max = max_sum;


        push current index into the BST;

    }else {

        //pseudo code steps to determine maximum possible sub array with the current element 

        //pre is inorder predecessor and succ is inorder successor

        get the inorder predecessor and successor from the BST;



        if(pre == NULL){

            max_sum = succ * current_array_value;


            if(max_sum > current_max)
            current_max = max_sum;


        }else if (succ == NULL){

            max_sum = (array_length - pre) - 1) * current_array_value;

            if(max_sum > current_max)
            current_sum = max_sum;

        }else {

        //find the maximum possible sub array streak from the values

        max_sum = [((succ - old_index) - 1) + ((old_index - pre) - 1) + 1] * current_array_value;

            if(max_sum > current_max)
            current_max = max_sum;

        } 

    }

Например,

исходный массив

                      1  5  3  5  4  1
                  -------------------------
 array indices =>     0  1  2  3  4  5  
                  -------------------------

и отсортированный массив

                                   1  1  3  4  5  5
                                 -------------------------
 original array indices =>         0  5  2  4  1  3  
 (referred as old_index)         -------------------------

После первого элемента:

max_sum = 6 [он уменьшится до 1 * 6]

        0

После второго элемента:

max_sum = 6 [он уменьшится до 1 * 6]

        0
         \
          5

После третьего элемента:

        0
         \
          5
         /
        2

результат обхода порядка: 0 2 5

применяя алгоритм,

max_sum = [((succ - old_index) - 1) + ((old_index - pre) - 1) + 1] * current_array_value;

max_sum = [((5-2) -1) + ((2-0) -1) + 1] * 3          = 12

current_max = 12 [максимально возможное значение]

После четвертого элемента:

        0
         \
          5
         / 
        2   
         \
          4

результат обхода порядка: 0 2 4 5

применяя алгоритм,

max_sum = 8 [который отбрасывается, так как он меньше 12]

После пятого элемента:

max_sum = 10 [уменьшается до 2 * 5, отбрасывается, так как оно меньше 8]

После последнего элемента:

max_sum = 5 [уменьшается до 1 * 5, отбрасывается, так как оно меньше 8]

Этот алгоритм будет иметь порядок алгоритма, который изначально используется для сортировки массива. Например, если исходный массив сортируется с двоичной сортировкой, он будет иметь O (n) в лучшем случае и O (n log n) в качестве среднего случая.

Сложность пространства будет O (3n) [O (n + n + n), n для отсортированных значений, другое n для старых индексов и другое n для построения BST]. Однако я не уверен в этом. Любая обратная связь по алгоритму оценивается.