Алгоритм - поиск начального индекса массива так, чтобы сумма элементов оставалась> = 0

Мне сказали, что это можно сделать за O (n) - за время и за O (n) - за использование памяти.

В качестве входных данных я получаю список зачинщиков (число n - доступно с самого начала).

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

* Сумма всех элементов в этом массиве всегда равна 0.

Как пример: 1, -1, -3, 3, 4, -4

  1. 1 - 1 - 3 = -2 <0 не тот
  2. -1 <0
  3. -3 <0
  4. 3 + 4 - 4 + 1 - 1 - 3 = 0

хорошо, потому что 7> 0, 3> 0, 4> 0, 3> 0, 0 = 0:)

То, как я делаю это сейчас, я иду в цикл N раз, внутри у меня есть две петли: один для индекса i-gt; другой для индекса 0-> i-1.

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

7 голосов | спросил Janek Walec 5 +03002016-10-05T14:18:15+03:00312016bEurope/MoscowWed, 05 Oct 2016 14:18:15 +0300 2016, 14:18:15

2 ответа


0

Из https://www.quora.com/Does-there -Всегда существовать-а-поворот в своем круговом массиве-такого-то, что все-префикс-сумма-для-тех-вращений-является-неотрицательным-Учитывая то из суммы из-все-ее -элементов-это-неотрицательное :

  

Пусть последовательность будет a (1), a (2), ..., a (N). Определить s_a (i) =   а (1) + а (2) + ... + а (я). Дано, что s_a (N) ≥0 (предположение). Пусть j будет   самый большой индекс, такой что s_a (j) <0, если такой j существует. Очевидно, J   & Lt; N Рассмотрим последовательность a (j + 1), a (j + 2), ..., a (N). Это легко увидеть   что все префиксные суммы этой последовательности равны ≥0. Если   a (j + 1) + a (j + 2) + ... + a (k) были меньше 0, s_a (k) было бы меньше   чем 0, а противоречие.

     

Теперь сгенерируйте новую последовательность {bi} =   а (J + 1), а (J + 2), ..., A (N), а (1), (2), ..., а (к). Легко видеть, что   суммы префиксов этой новой последовательности (назовите ее s_b (i)) не достигают   значение меньше нуля для первых N-й элементов. Кроме того, так как   s_b (N-j) ≥0, если бы s_a (i) был неотрицательным, s_b (i + N-j) также был бы.

     

Продолжайте повторять процесс взятия раздела после самого правого   позиция с отрицательной суммой префикса и приведение ее к началу   последовательности. На каждом этапе стартовый диапазон, в котором мы находимся   уверенный, что суммы префикса будут неотрицательными, продолжает увеличиваться. Но   это число ограничено N, длиной последовательности. Это означает   что после некоторых шагов в префиксе не будет отрицательной суммы префикса   последовательность. Таким образом, мы получили поворот исходной последовательности   со всеми префиксными суммами неотрицательными.

Это простая реализация O (n) для моей идеи.

int best_index(std::vector<int> & a){
    int n = A.size();

    long long array_sum=0;
    long long sum=0;
    int last_index=-1;
    for (int i = 0; i < n; ++i)
    {
        array_sum+=a[i];
        if (sum<0)
        {
            sum=0;
            if (a[i]>=0)
            {
                last_index=i;
            }
        }
        sum+=a[i];
    }

    if (array_sum<0)
    {
        return -1;
    }
    return last_index;
}

Сложность: O (n)

ответил v78 5 +03002016-10-05T14:29:05+03:00312016bEurope/MoscowWed, 05 Oct 2016 14:29:05 +0300 2016, 14:29:05
0

Начнем с накопления суммы элементов:

elements = [1, -1, -3, 3, 4, -4]
sums =     [1,  0, -3, 0, 4,  0]

(Если последнее значение отрицательно, решения не существует)

Итак, если бы мы начали с индекса 0, мы бы получили эту последовательность. Если бы мы начали с индекса 1, все числа уменьшились бы на единицу (и вращались бы вокруг, но нас это не волнует). Если бы мы начали с индекса 2, цифры не были бы другими. Мы можем видеть, что, выбирая начальную точку, мы можем перемещать всю последовательность вверх и вниз по значениям пропущенных чисел.

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

Это легко найти в O(n):

startingIndex (elements):
    sums = []
    sum = 0
    for (i = 0; i < elements.length; i++)
        sums[i] = sum
        sum += elements[i]
    if (sum < 0)
        throw "invalid input"
    min = 0
    index = 0
    for (i = 0; i < elements.length; i++)
        if (sums[i] < min)
            min = sums[i]
            index = i
    return index
ответил Bergi 5 +03002016-10-05T14:58:22+03:00312016bEurope/MoscowWed, 05 Oct 2016 14:58:22 +0300 2016, 14:58:22

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132