c - How can I reduce time complexity of the following program? -

question:

mark undergraduate student , interested in rotation. conveyor belt competition going on in town mark wants win. in competition, there's conveyor belt can represented strip of 1xn blocks. each block has number written on it. belt keeps rotating in such way after each rotation, each block shifted left of , first block goes last position.

there switch near conveyer belt can stop belt. each participant given single chance stop belt , pmean calculated.

pmean calculated using sequence there on belt when stops. participant having highest pmean winner. there can multiple winners.

mark wants among winners. pmean should try guarantees him winner.

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

where represents configuration of conveyor belt when stopped. indexing starts 1.

input format

first line contains n denoting number of elements on belt.   second line contains n space separated integers. 

output format

output required pmean 

constraints

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

for rotation, pmean lie within range of 64-bit signed integer.

sample input

3 20 30 10  

sample output

140 

explanation

number on top can written in these manners.

initial numbers on belt, `

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

after first rotation,

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

after second rotation,

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

so maximum possible value 140.

code:

 #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; } 

the code fine takes time execute. how can reduce complexity n^2 lower one?

after thinking sometime got answer:

#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; }