动态规划算法之一维数组前缀和

function calculatePrefixSum(array) {  
   const prefixSumArray = new Array(array.length + 1).fill(0); // 初始化长度为array.length + 1的前缀和数组，并全部填充为0  
   for (let i = 0; i < array.length; i++) {  
       prefixSumArray[i + 1] = prefixSumArray[i] + array[i]; // 计算前缀和，注意索引+1  
   }  
   return prefixSumArray;  
}  
 
// 示例用法  
const array = [1, 2, 3, 4, 5];  
const prefixSumArray = calculatePrefixSum(array);  
 
console.log("原始数组:", array);  
console.log("前缀和数组:", prefixSumArray);  
 
// 计算从索引i到索引j（包含j）的子数组的和  
function sumSubarray(prefixSumArray, i, j) {  
   return prefixSumArray[j + 1] - prefixSumArray[i]; // 注意索引+1  
}  
 
const i = 1; // 子数组的起始索引（从0开始）  
const j = 3; // 子数组的结束索引（从0开始）  
const subarraySum = sumSubarray(prefixSumArray, i, j);  
console.log(`子数组(${i}, ${j}) 的和: ${subarraySum}`);