Поиск алгоритма для хранения конкретных сумм элементов массива несколько раз

Question

Решение проблемы 15 в Project Euler, я борюсь с последней проблемой при реализации моего алгоритма. Я пропустил последний шаг. Я использую Java, но мне нужна только общая идея.

Предположим, что мы имеем примитивный массив как где п = 20:

long[] a = new long[20]; 

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

Предположим, у нас есть порядок, как это:

a[19] = ... ; 
    a[18] = ... ; 
    ... 
    ... 
    a[0] = ... ; 

Следующие элементы последовательности должны выглядеть следующим образом:

long[] b = new long[20]  

    for(int i = a.length - 1; i >= 0; i--){ 

    b[19] += a[i]; 

    } 

    for(int i = a.length - 2 ; i >= 0; i--){ 

    b[18] += a[i]; 

    } 
    ... 

Идея состоит в том, что верхний элемент массива sequence b, в соответствии с вышеприведенным порядком, всегда является суммой всех элементов массива a. Элемент под верхним элементом хранит все элементы массива a EXCEPT верхнего. Таким образом, это в основном суммирование их в порядке убывания/возрастания. Поэтому b [0] = a [0]. Следующие элементы последовательности будут тогда суммами элементов массива b и т. Д.

Проблема в том, что мне нужно будет повторить это n раз для произвольных сеток.

Как это сделать?

Answer 1

Попробуйте это

long[] b = new long[20]; 
b[0] = a[0]; 

for(int i = 1; i < b.length; i++){ 
    b[i] = b[i-1] + a[i]; 
} 

вышеупомянутые утилиты это соотношение b(n) = b(n-1) + a(n)