Оптимальное решение для непрерывной суммы элементов массива - PullRequest
Новая
       10

Оптимальное решение для непрерывной суммы элементов массива

0 голосов
/ 26 августа 2018

Может кто-нибудь предложить оптимальное решение для следующей проблемы. Учитывая массив положительных / отрицательных целых чисел, верните максимальную «специальную сумму». Для данного массива A «Специальная сумма» в каждом индексе массива определяется следующим образом. 

S[i] = S[i] + (S[i+1] + S[i+2]) + (S[i+3] + S[i+4] + S[i+5]) + (S[i+6] + S[i+7] + S[i+8] + S[i+9]) + .....

т.е. К элементу с индексом i мы добавляем следующие 2 элемента, затем следующие 3, затем следующие 4, пока в массиве не будут доступны эти подмножества чисел.

например; Array A [1 3 1 2 5 -5] => Результат: 8 Объяснение: 

S[0] = 1+(3+1)+(2+5-5)=7;
s[1] = 3+(1+2)=6;
S[3] = 1+(2+5)=8; 
S[4] = 2+(5-5)=2; 
S[5] = 5; S[6] = -5;

Поскольку S [3] является максимальным, это результат. Это можно решить с помощью 3loops, есть ли оптимальный способ решить это?

1 Ответ

0 голосов
/ 29 ноября 2018

часть 1

Данный массив S длины N рассмотрим следующую последовательность: 

R[i] = S[i+1] + s[i+2] + s[i+3] + ... + s[N-1] + s[N]
       R[i+1] = S[i+2] + s[i+3] + ... + s[N-1] + S[N]

                   ...
                                        R[N-1] = S[n]

Это означает, что R [k] = S [k] + R [k + 1]

№ петли 1: 

from N to 0 do:
  R[k] = s[k]
  if R[k+1] exists do
    R[k] = R[k] + R[k+1]

Например, если сумма N = 9 отражена через x на диаграмме ниже: 

     123456789
S[0] xxxxxxxxx   
S[1]  xxxxxxxx   
S[2]   xxxxxxx   
S[3]    xxxxxx      
S[4]     xxxxx      
S[5]      xxxx      
S[6]       xxx        
S[7]        xx        
S[8]         x

часть 2

Мы предполагаем, что количество элементов, суммируемых в строке, должно быть треугольным числом (элемент последовательности 1 + 2 + 3 ..., допустимые элементы 1,3,6,10, ...)

Для наглядности возьмем наш пример: 

     123456789
S[0] xxxxxx   
S[1]  xxxxxx   
S[2]   xxxxxx   
S[3]    xxxxxx      
S[4]     xxx      
S[5]      xxx      
S[6]       xxx        
S[7]        x        
S[8]         x

Обратите внимание, что в каждом ряду (с индексом i) в конце могут быть пробелы. Пробелы возникают, когда число N-i не является треугольным.

Например, по индексу i=0: N-i = 9, наибольшее треугольное число меньше 9 равно 6

Чтобы получить наименьшее треугольное число, соответствующее числу, используйте FLOOR по следующей формуле:

enter image description here

function closest_triangle(n)
  ((sqrt(8*n+1) -1) / 2).floor
end

часть 2 Теперь просто переберите все R [i], где i = 0 ... N, и вычтите ненужные части: 

for i in 0..N
  for j in 0..closest_triangle(N-i)
    R[i] = R[i] - S[i + j + 1]
  end
end

Конечно, вы можете хранить частичные суммы вычитания, так как они будут повторяться. Например, если N = 21: 

xxxxxxxxxxxxxxxxxxxxx      
 xxxxxxxxxxxxxxx      
  xxxxxxxxxxxxxxx      
   xxxxxxxxxxxxxxx      
    xxxxxxxxxxxxxxx      
     xxxxxxxxxxxxxxx      
      xxxxxxxxxxxxxxx           
       xxxxxxxxxx           
        xxxxxxxxxx           
         xxxxxxxxxx           
          xxxxxxxxxx           
           xxxxxxxxxx               
            xxxxxx               
             xxxxxx               
              xxxxxx               
               xxxxxx                  
                xxx                  
                 xxx                  
                  xxx                    
                   x                    
                    x

Так что это упростит вычисления (сохраняя сумму некоторых из последних чисел).

Теперь по сложности:

В первой части мы создаем массив размером N и выполняем элементарные операции N.

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

Таким образом, алгоритм достигнет сложности O (n)

...