Sum of all contiguous subarrays optimisation

Question

I am solving a problem where I have an array and for two given indices min and max, I need to find sum of all contiguous sub-arrays between them.

All I could think is of this O(n²) code

for (int i = min; i <= max; ++i)
{
    long long sum = 0;
    for (int j = i; j <= max; ++j)
    {
        sum += a[j];
        printf("%lld\n", sum);
    }
}

Can anyone please help me with optimising this code?

Answer 1

Using dynamic programming you can achieve O(n) answer. The idea basically is to calculate prefix sums accumulated for all elements.

Let A(i) be the summation of elements from 0 to i. This can be calculated easily in O(n) by:

// let your array by Src[Max]
int A[MAX];
A[0] = Src[0];

for(int i = 1; i < MAX; i++) {
    A[i] += A[i - 1] + (i + 1) * Src[i];
}

Then for any elements i and j, you can calculate sum(i,j) = A[j] - A[i] (adjust for boundaries depending on input requirements).

Answer 2

There is no faster solution.

Since your output size is O(n²), not algorithm can be faster.