Finding an algorithm for storing specific sums of elements of array multiple times

Question

Tackling Problem 15 at Project Euler, I am struggling with the last problem at the implementation of my algorithm. I am missing one last step. I am using Java, but I only need to get the general idea.

Suppose we have a primitive array like where n = 20:

    long[] a = new long[20]; 

Numbers that are stored in the array directly determine the next sequence of numbers (or routes in this context). To be more clear, let me give you an example of what I mean:

Suppose we have an order like this:

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

The next sequence elements should look like this:

   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]; 

    }
   ...

The idea is that the top element of the sequence array b, according the order above, is always the sum of all elements of array a. The element below the top element stores all of array a's elements EXCEPT the top one. So it's basically summing them up in an descending/ascending order . Therefore b[0] = a[0] as well. The next sequence elements will then be sums of elements of array b and so on...

The problem is that I will need to be able to repeat this n times for arbitrary grids.

How do I go about this?

Answer 1

Try this

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

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

Above utilities this relation b(n) = b(n-1) + a(n)