一道PAT 1049数列的片段和 运行超时

测试积点老人

1049 数列的片段和 (20 分)
给定一个正数数列，我们可以从中截取任意的连续的几个数，称为片段。例如，给定数列 { 0.1, 0.2, 0.3, 0.4 }，我们有 (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 这 10 个片段。
给定正整数数列，求出全部片段包含的所有的数之和。如本例中 10 个片段总和是 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0。

1. /**
   
2. 统计数列中每个元素出现的次数，然后乘以这个数列元素，再求和。
   
3. 那么对于求每个元素出现的次数这个问题，我们先假定由这么一个数列，我们从1到n依次为其元素建立索引值，例如第一个元素索引值就是1，最后一个就是n。使用数组来存储这个数列时，数组的索引值时会被-1的，所以要再加上1。
   
4. 对于其中的任意一个元素，假设其索引值为i。发现若数列片段的首项的索引值超过i时，这个片段一定不会“囊括”该元素；同时发现，当数列片段的首项的索引值不超过i时（不妨假设为k，称之为次首项数列），所有的以k为首项的数列片段，一定都“囊括”了该元素，且“囊括”的次数由从该元素开始到数列尾项的个数决定，即（n-i+1）次（与首项索引值无关，称之为囊括次数）。那么该元素总共出现的次数就是这样所有的次首项数列的个数乘以囊括次数。那么该元素在片段和总和中造成的影响即为该元素值ai*(n-i+1)*i
   
5. */
   
6. import java.util.Scanner;
   
7. import java.text.DecimalFormat;
   
8. public class Main{
   
9.     public static void main(String[] args){
   
10.         Scanner scan=new Scanner(System.in);
    
11.         int n=scan.nextInt();
    
12.         double sum=0;
    
13.         double[] a=new double[n];
    
14.         DecimalFormat df=new DecimalFormat("0.00");
    
15.         for(int i=0;i<n;i++) a[i]=scan.nextDouble();
    
16.         for(int i=0;i<n;i++){
    
17.             sum+=a[i]*(i+1)*(n-i);
    
18.         }
    
19.         String str=df.format(sum);
    
20.         System.out.println(str);
    
21.     }
    
22. }
    
23. 我原来的代码是三循环，超时了，但是这个为什么也会超时？不会超时的算法应该是什么？

复制代码

qqq911

试试分段计算呢