长安网站建设费用,网站建设视频万网,wordpress 欢迎插件,网站建设期末试卷1588. 所有奇数长度子数组的和
给你一个正整数数组 arr #xff0c;请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。
示例 1#xff1a;
输入#xff1a;arr [1,4,2,5,3] 输出#xff1…1588. 所有奇数长度子数组的和
给你一个正整数数组 arr 请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。
示例 1
输入arr [1,4,2,5,3] 输出58 解释所有奇数长度子数组和它们的和为 [1] 1 [4] 4 [2] 2 [5] 5 [3] 3 [1,4,2] 7 [4,2,5] 11 [2,5,3] 10 [1,4,2,5,3] 15 我们将所有值求和得到 1 4 2 5 3 7 11 10 15 58
示例 2
输入arr [1,2] 输出3 解释总共只有 2 个长度为奇数的子数组[1] 和 [2]。它们的和为 3 。
示例 3
输入arr [10,11,12] 输出66
提示
1 arr.length 1001 arr[i] 1000
解题思路
维护一个前缀和然后遍历所有奇数长度的子数组统计出总和
代码
class Solution {public int sumOddLengthSubarrays(int[] arr) {int narr.length;int[] dpnew int[n1];dp[0]0;for(int i1;in;i)dp[i]dp[i-1]arr[i-1];int res0;for(int len1;lenn;len2){for(int ilen;in;i)resdp[i]-dp[i-len];}return res;}
}
