Sum of all continuous optimization of the sub-machine
I solve a problem when I have a larger array and for a given two numbers I need to find the sum of all adjacent subarrays in between.
All I could think of was O (n 2 ) code
for(i = min; i<= max; ++i)
{
sum = 0;
for(j = i; j <= max; ++j)
{
sum+=a[j];
printf("%lld\n", sum);
}
}
Can anyone help me optimize this code?
source to share
Using dynamic programming you can get the answer O(n)
. The basic idea is to calculate the prefix sums accumulated for all elements.
Let be the A(i)
summation of elements from 0
to i
. It can be easily computed in O (n) like this:
// 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 the boundaries depending on the input requirements).
source to share