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 <= 100
• 1 <= arr[i] <= 1000

解題思路

維護一個前綴和，然后遍歷所有奇數長度的子數組，統計出總和

代碼

class Solution {public int sumOddLengthSubarrays(int[] arr) {int n=arr.length;int[] dp=new int[n+1];dp[0]=0;for(int i=1;i<=n;i++)dp[i]=dp[i-1]+arr[i-1];int res=0;for(int len=1;len<=n;len+=2){for(int i=len;i<=n;i++)res+=dp[i]-dp[i-len];}return res;}
}