c - 如何降低以下程序的时间复杂度？

Question

问题:

马克是一名本科生，他对轮换感兴趣。镇上正在举行传送带比赛，马克希望获胜。在比赛中，有一条传送带，可以表示为一条由 1xN block 组成的 strip 。每个 block 上都写有一个数字。传送带不断旋转，每次旋转后，每个 block 都会向其左侧移动，第一个 block 到达最后一个位置。

传送带附近有一个开关，可以停止传送带。每个参与者都有一次停止传送带的机会，并且将计算他的 PMEAN。

PMEAN 是使用皮带停止时的序列来计算的。 PMEAN 最高的参与者是获胜者。可能有多个获胜者。

马克希望成为获胜者之一。他应该努力获得什么 PMEAN 才能保证他成为获胜者。

PMEAN=∑i=1ni×a[i]

其中a表示传送带停止时的配置。索引从1开始。

输入格式

First line contains N denoting the number of elements on the belt. 

Second line contains N space separated integers.

输出格式

Output the required PMEAN

约束

1 ≤ N ≤ 10^6 
-10^9 ≤ each number ≤ 10^9 

对于任何旋转，PMEAN 将始终位于 64 位有符号整数的范围内。

示例输入

3
20 30 10 

示例输出

140

说明

上面的数字可以用这些方式写。

腰带上的初始数字，`

20 30 10 
PMEAN = 1x20 + 2x30 + 3x10 = 110` 

第一次旋转后，

30 10 20 
PMEAN = 1x30 + 2x10 + 3x20 = 110 

第二次旋转后，

10 20 30 
PMEAN = 1x10 + 2x20 + 3x30 = 140 

因此最大可能值为 140。

代码:

 #include <stdio.h>

int main() {

    int n,i;
    scanf("%d",&n);
    int b[n],a[n],k,ans,temp;
    int *sum = calloc(n,sizeof(int)) ;
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(k=0;k<n;k++){
    for(i=0;i<n;i++){
        b[i] = a[(i+k)%n];
        sum[k]+= (i+1)*b[i];
    }
        if(ans<sum[k] || k==0){
            ans = sum[k];
        }
    }
    printf("%d",ans);
    return 0;
}

代码很好，但执行时间太长。如何将其复杂度从 N^2 降低到更低的一个？

Answer 1

经过思考一段时间，我得到了答案:

#include <stdio.h>

int main() {

    int n,i,k;
    scanf("%d",&n);
    long long int a[n],sum[n], ans, s=0,temp;
    sum[0] =0;
    for(i=0;i<n;i++){
        scanf("%lld",&a[i]);
        sum[0]+=(i+1)*a[i];
        s+= a[i];
    }
    ans = sum[0];
    for(k=1;k<n;k++){
        temp = n*a[k-1];
        sum[k]= sum[k-1] - s + temp;
        if(ans<sum[k])
            ans = sum[k];
    }


    printf("%lld",ans);
    return 0;
}