このアルゴリズムをより効率的にするにはどうすればよいですか？

Question

私は可能なすべての値の合計を含む2次元配列を生成するアルゴリズムを持っています。たとえば、配列[1,5,8,4,5]の場合、2D配列sums[1][3]は、元の配列（17）のインデックス1-3の合計を返す必要があります。大きなOに関して、効率はO（N ）と考えています。このアルゴリズムをより効率的にする方法はありますか？

public static int[][] sum(int[] values){ 
    int[][] sums = new int[values.length][values.length]; 
    for(int x = 0; x < values.length; x++){ 
     int total = 0; 
     for(int y = x; y < values.length; y++) { 
      total += values[y]; 
      sums[x][y] = total; 
     } 
    } 
    return sums; 
} 

Answer 1

あなたは接頭和アレーでO(n)時間と空間でこれを解決することができます。

array = [1, 5, 8, 4, 5] 
prefixes = [1, 6,14,18,23] 

sums(1,3) = prefixes[3] - prefixes[0] = 18 - 1 = 17 

Answer 2

計算し、次のようにprefix合計：あなたのクエリを1として

public static int[] sum(int[] values){ 
    int[] prefix_sums = new int[values.length]; 
    prefix_sums[0] = values[0]; 
    for(int x = 1; x < values.length; x++){ 
     prefix_sums[x] = prefix_sums[x-1] + values[x]; 
    } 
    return prefix_sums; 
} 

、インデックスxからインデックスy（0ベースのインデックス作成）までの合計を求めたい場合は、合計を取得する方法です。

if(x==0) 
    result = prefix_sums[y]; 
else 
    result = prefix_sums[y] - prefix_sums[x-1]; 

希望する！