Ruby Сложность / Время объяснения

Question

Я использую HackerRank, чтобы улучшить свои навыки рубина. У меня проблема с структурами данных - манипулирование массивом: https://www.hackerrank.com/challenges/crush/problem

Мое решение указано первым, предположительно «правильное» решение, которое я не смог реализовать, указано в списке последним. Мое решение работает для всех тестовых случаев, кроме ** ОЧЕНЬ ** больших чисел, оно не выполняется из-за тайм-аута Я знаю, что это из-за цикла, но кто-то может предложить другое решение и объяснить, почему их работает?

ОБЪЯСНЕНИЕ ПРОБЛЕМЫ:

Пример ввода

5 3
1 2 100
2 5 100
3 4 100
#n=5 m=3, then following numbers leftIndex=1 rightIndex=3 sum=100 and so on

Пример вывода

200

Объяснение

After the first update list will be 100 100 0 0 0. 
After the second update list will be 100 200 100 100 100. 
After the third update list will be 100 200 200 200 100. 
The required answer will be 200. 

OR

Объясните, почему нижнее решение может работать без циклов?

#Problem Data Set, my solution times out for the listed data set

10000000 100000
[
 [1400906,9889280,90378],
 [6581237,9872072,87106],
 [4386373,9779851,52422],
 [198648,4373818,5289]
]
# For this problem, variables will look like:
n = 10000000
m = 100000
q = [[1400906,9889280,90378],[6581237,9872072,87106],[4386373,9779851,52422],[198648,4373818,5289]]


def arrayManipulation(n, q)
  arr = Array.new(n,0)
  max = 0
  q.size.times do |i|
    left, right, value = q[i][0],q[i][1],q[i][2]
    left -= 1
    (left...right).each do |j|
      arr[j] += value
      max = arr[j] if max < arr[j]
    end
  end
  return max
end
# this times out on HackerRank, please explain better solution, 
#or why the bottom solution works!

result = arrayManipulation n, queries

Рабочее решение на доске обсуждений

N, M = gets.chomp.split(' ').map(&:to_i)

# create array of zeros of length N + 1
arr = Array.new(N + 1, 0)

M.times do
  # cycle through and get the inputs
  start, finish, value = gets.chomp.split(' ').map(&:to_i)

  # increment value at start of sequence
  arr[start - 1] += value

  # decrement value at first position after sequence
  arr[finish] -= value
end

tmp = 0
max = 0

arr.each do |value|
  # step through summing array
  tmp += value

  # capture the max value of tmp
  max = tmp if max < tmp
end

puts max

Answer 1

Ваш код O(m * n), поскольку у вас есть вложенный цикл для обновления массива для каждой записи.

Рабочий код: O(m + n): он никогда не хранит массив, он хранит дельта-массив, массив изменений, который позволяет восстановить массив. В вашем первом примере он будет хранить:

0    0    0    0    0   0
+100 0    -100 0    0   0
+100 +100 -100 0    0   -100
+100 +100 0    0   -100 -100

Для этого требуется только цикл m итераций, без вложенных циклов; затем вам понадобится еще один цикл из n итераций, чтобы пройти через массив, продолжить подсчет итогов и определить его максимум.