所有邻接子阵优化之和

Question

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

Answer 1

使用动态编程，可以实现O(n)答案。其基本思想是计算所有元素的前缀总和。

设A(i)是从0到i的元素的总和。这可以在O(n)中很容易地计算，方法是：

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

然后对于任何元素i和j，可以计算sum(i,j)=a[j]-a[i]（根据输入需求调整边界）。