title: How can I reduce time complexity of the following program?
body: <p><strong>Question:</strong></p>
  
  <p>Mark is an undergraduate student and he is interested in rotation. A conveyor belt competition is going on in the town which Mark wants to win. In the competition, there's A conveyor belt which can be represented as a strip of 1xN blocks. Each block has a number written on it. The belt keeps rotating in such a way that after each rotation, each block is shifted to left of it and the first block goes to last position.</p>
  
  <p>There is a switch near the conveyer belt which can stop the belt. Each participant would be given a single chance to stop the belt and his PMEAN would be calculated.</p>
  
  <p>PMEAN is calculated using the sequence which is there on the belt when it stops. The participant having highest PMEAN is the winner. There can be multiple winners.</p>
  
  <p>Mark wants to be among the winners. What PMEAN he should try to get which guarantees him to be the winner.</p>
  
  <pre><code>PMEAN=∑i=1ni×a[i]
  </code></pre>
  
  <p>where a represents the configuration of conveyor belt when it is stopped. Indexing starts from 1.</p>
  
  <p><strong>Input Format</strong> </p>
  
  <pre><code>First line contains N denoting the number of elements on the belt. 
  
  Second line contains N space separated integers.
  </code></pre>
  
  <p><strong>Output Format</strong> </p>
  
  <pre><code>Output the required PMEAN
  </code></pre>
  
  <p><strong>Constraints</strong> </p>
  
  <pre><code>1 ≤ N ≤ 10^6 
  -10^9 ≤ each number ≤ 10^9 
  </code></pre>
  
  <p>For any rotation, PMEAN will always lie within the range of 64-bit signed integer.</p>
  
  <p><strong>Sample Input</strong></p>
  
  <pre><code>3
  20 30 10 
  </code></pre>
  
  <p><strong>Sample Output</strong></p>
  
  <pre><code>140
  </code></pre>
  
  <p><strong>Explanation</strong></p>
  
  <p>Number on top can be written in these manners. </p>
  
  <p>Initial numbers on belt, `</p>
  
  <pre><code>20 30 10 
  PMEAN = 1x20 + 2x30 + 3x10 = 110` 
  </code></pre>
  
  <p>After first rotation, </p>
  
  <pre><code>30 10 20 
  PMEAN = 1x30 + 2x10 + 3x20 = 110 
  </code></pre>
  
  <p>After second rotation, </p>
  
  <pre><code>10 20 30 
  PMEAN = 1x10 + 2x20 + 3x30 = 140 
  </code></pre>
  
  <p>So maximum possible value will be 140.</p>
  
  <p><strong>Code:</strong></p>
  
  <pre><code> #include &lt;stdio.h&gt;
  
  int main() {
  
      int n,i;
      scanf("%d",&amp;n);
      int b[n],a[n],k,ans,temp;
      int *sum = calloc(n,sizeof(int)) ;
      for(i=0;i&lt;n;i++){
          scanf("%d",&amp;a[i]);
      }
      for(k=0;k&lt;n;k++){
      for(i=0;i&lt;n;i++){
          b[i] = a[(i+k)%n];
          sum[k]+= (i+1)*b[i];
      }
          if(ans&lt;sum[k] || k==0){
              ans = sum[k];
          }
      }
      printf("%d",ans);
      return 0;
  }
  </code></pre>
  
  <p>The code is fine but takes too much time to execute. How can I reduce its complexity from N^2 to lower one?</p>