Логика, используемая позади Массирование Массив HackerRank

Ответ 1

В основном мы храним приращение в начальной позиции и после последнего индекса в диапазоне. Для a b k мы увеличим +k для всех элементов в индексе [a,b], но тогда следующие элементы не будут увеличены. Таким образом, мы вычитаем это, потому что при предыдущем увеличении все элементы справа от диапазона будут меньше на -k. Мы в основном сохраняем все конечные значения с помощью этого увеличения/уменьшения.

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

Первоначально массив будет 0 0 0 0 0.

После первой операции 1 3 3 первоначально элементы массива должны быть 3 3 3 0 0 но мы храним это так

3 0 0 -3 0

Значение

First element is 3 greater than 0.
Second  ->       0 greater than index 1 element.
Third   ->       0 greater than index 2 element
Fourth  ->      -3 greater than index 3 element.
fifth   ->       0 greater than index 4 element.

После второй операции 2 4 4 первоначально массив будет 3 7 7 4 0, но мы сохраняем его следующим образом 3 4 0 -3 -4. Точно так же, как я описал подробно, имейте в виду, что, думая так, вы увидите, что мы не теряем информацию. Мы просто храним его по-другому.

Окончательные значения будут

0+(3) 0+3+(4) 0+3+4+(0) 0+3+4+0+(-3) 0+3+4+0-3+(-4)

3  7    7       4           0  matches with what we got earlier.

Обратите внимание, как мы рассчитываем каждый элемент. Просто добавьте предыдущий элемент со значением, на которое текущий элемент больше.

Обратите внимание, что это решение работает, потому что оно запрашивается только один раз. Если он запрашивается m раз, то это решение не работает, потому что время ожидания истекло. Затем вам придется копать глубже, используя сложные структуры данных, такие как деревья сегментов и/или деревья с двоичными индексами.

Ответ 2

Я попытаюсь объяснить свое понимание этого:
Каждая строка ввода в основном описывает последовательность, и вас просят найти максимальное значение суммы этих последовательностей.
Например, если N задано как 5:
линия 2 4 13 описывает последовательность [0, 13, 13, 13, 0]
линия 3 5 11 описывает последовательность [0, 0, 11, 11, 11].
Если это единственные линии, мы получаем последовательность результатов из точечной суммы двух, которая равна [0, 13, 24, 24, 11].

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

В случае вышеуказанных последовательностей разностные последовательности:
[0, 13, 0, 0, -13] для последовательности, описываемой 2 3 13
[0, 0, 11, 0, 0] для последовательности, описываемой 3 5 11
[0, 13, 11, 0, -13 для суммы последовательностей.

Важным свойством является разностная последовательность суммы последовательностей - это сумма разностных последовательностей.

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

Хотя пример, который я дал, имеет только 2 строки, эта же идея работает для любого количества строк.

Надеюсь, это дает хорошую интуицию относительно идеи решения.

Ответ 3

Эти два места помогли мне лучше понять этот алгоритм. Prefix_sum_array_and_difference_array
Переполнение стека

Если вы хотите простое и прямое объяснение: начальный, массив 0 0 0 0 0 cpp after the first operation, 1 2 100 it will become seq1:100 100 0 0 0 and after second 2 5 100 seq2: 0 100 100 100 100 and after 3 4 100 seq2: 0 0 100 100 0 но когда мы применяем матрицу разностей на каждом шаге, мы получим

cpp diff seq of seq1:100 0 -100 0 0 diff seq of seq2: 0 100 0 0 0 -100 diff seq of seq3: 0 0 100 0 -100

Важным свойством является разностная последовательность суммы последовательностей - это сумма разностных последовательностей.

он даст нам, cpp 100 100 0 0 -100 -100(for clarity purpose only) или вы можете добавить все последовательности в виде cpp seq1+seq2+seq3 = 100 200 200 200 100 а затем найти разницу seq или который равен 100 100 0 0 -100, а затем найдите префиксный массив.

Почему мы игнорируем первые 100? Прочитайте первую статью о разностном массиве и массиве префикс sum !!!!

и после этого сделайте префикс sum cpp 100 200 200 200 100 0 Игнорируйте последний 0, поскольку последний индекс, который мы рассмотрели, предназначен только для ясности.

поэтому оба эти шага найдут для нас разностный массив :) cpp a[p]+=sum; if((q+1)<=N) a[q+1]-=sum; cpp a[p]+=sum; if((q+1)<=N) a[q+1]-=sum;

Ответ 4

Следующий код работал для меня в C++. Я взял некоторую помощь онлайн и затем закодировал это.

long arrayManipulation(int n, vector<vector<int>> queries) {
  vector<long> resultVector(n);
  long maxVal=0, x=0, i;

  for(int i = 0; i<n ; i++)
  {
      resultVector[i]=0;
  }

  for(i=0; i<queries.size(); i++)
  {
      resultVector[(queries[i][0])-1] += queries[i][2];

      if((queries[i][1]) <= n)
      {
          resultVector[(queries[i][1])] -= queries[i][2];
      }
  }

  for(i=0; i <n; i++)
  {
      x+=resultVector[i];
      if(x>maxVal)
      {
          maxVal=x;
      }
  }

  return maxVal;
}

Ответ 5

Before solving this problem you must know Prefix Sum Array & Difference array. 

consider below case
a b k
1 5 3
4 8 7
6 9 1 

# if we calculate original array 'A' from this it will be
[3,3,3,10,10,8,8,8,1,0]

# now, lets find out the difference array 'D(A)'
[3,0,0,7,0,-2,0,0,-7,-1]

# follow below steps & calculate the array
A[a] += k
A[b+1] -= k , b+1 < len(A)
you will get [3,0,0,7,0,-2,0,0,-7,-1] which is D(A) itself.

# P(0, D(A)) = A. i.e. calculate prefix sum array of D(A). you will get the original array.
[3,3,3,10,10,8,8,8,1,0]

return max :)

Ответ 6

вместо добавления k ко всем элементам в диапазоне от a до b в массиве, накапливайте массив разностей

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

ex- n = 5, m = 1, a = 2 b = 5 k = 5

    i     0.....1.....2.....3.....4.....5.....6   //take array of size N+2 to avoid index out of bound
  A[i]    0     0     0     0     0     0     0

Добавьте k = 5 к a = 2

A [a] = A [a] +k//начальный индекс, откуда следует добавить элемент k, аналогично a [p] + = sum;

     i    0.....1.....2.....3.....4.....5.....6 
   A[i]   0     0     5     0     0     0     0

Теперь примените алгоритм суммирования префиксов

     i    0.....1.....2.....3.....4.....5.....6 
  A[i]    0     0     5     5     5     5     5

так что вы можете видеть добавление K = 5 ко всему элементу до конца после применения префиксной суммы, но нам не нужно добавлять k до конца. поэтому, чтобы свести на нет этот эффект, мы должны добавить -K также после индекса b + 1, так что только из диапазона [a, b] будет добавлен эффект добавления элемента K.

A [b + 1] = A [b] -K//для удаления эффекта ранее добавленного элемента k после b-го индекса (аналогично [q + 1] - = sum;), поэтому добавление -K в начальный массив вместе с +k.

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     0     0     0    -5

Теперь примените префикс sum Array

    i    0.....1.....2.....3.....4.....5.....6 
  A[i]   0     0     5     5     5     5     0

Вы можете видеть, что теперь K = 5 было добавлено от a = 2 до b = 5, что и ожидалось. Здесь мы обновляем только два индекса для каждого запроса, поэтому сложность будет O (1).

Теперь примените тот же алгоритм на входе

         # 0.....1.....2.....3.....4.....5.....6    //taken array of size N+2 to avoid index out of bound
5 3      # 0     0     0     0     0     0     0
1 2 100  # 0    100    0   -100    0     0     0       
2 5 100  # 0    100   100  -100    0     0   -100
3 4 100  # 0    100   100    0     0  -100   -100

Чтобы вычислить максимальную сумму префикса, накопите массив разностей до to, принимая максимальный накопленный префикс.

После выполнения всех операций теперь применяется префикс sum Array

    i      0.....1.....2.....3.....4.....5.....6 
  A[i]     0     100   200  200   200   100    0

Теперь вы можете обойти этот массив, чтобы найти максимальное значение, равное 200. Обход массива займет O (N) времени, а обновление двух индексов для каждого запроса займет O (1) * количество запросов (м).

общая сложность = O (N) +O (M) = O (N + M)

это означает = (10 ^ 7 + 10 ^ 5), что меньше 10 ^ 8 (в секунду)

Примечание: если вы ищете видеоурок, вы должны проверить его здесь для подробного объяснения.

Ответ 7

Он использует концепцию Array Difference. Это новая концепция для добавления значения в данный диапазон (i, j, k). i и j определяют диапазон, а k - это значение, которое будет добавлено. Будет очень полезно, если вы проверите ссылку.https://www.geeksforgeeks.org/difference-array-range-update-query-o1

Ответ 8

#include<stdio.h>
#include<stdlib.h>
int main()
{
    long int i,n,m,a,b,k,large,p[10^7],j,c[3];
    scanf("%ld\t%ld\n",&n,&m);
    for(i=1;i<=n;i++)
    p[i]=0;
    for(i=1;i<=m;i++)
    {
        scanf("%ld\t",&a);
        scanf("%ld\t",&b);
        scanf("%ld\n",&k);
        if((a<=b)&&(b<=n))
        {
            for(j=a;j<=b;j++)
            p[j]+=k;
        }
    }
    large=p[1];
    for(i=2;i<=n;i++)
    {
        if(p[i]>large)
        large=p[i];
    }
    printf("%ld",large);
    return 0;
}