來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays
題目描述：
給你一個正整數(shù)數(shù)組 arr 氮发，請你計算所有可能的奇數(shù)長度子數(shù)組的和。
子數(shù)組 定義為原數(shù)組中的一個連續(xù)子序列琳省。
請你返回 arr 中 所有奇數(shù)長度子數(shù)組的和 徊都。
示例 1：
輸入：arr = [1,4,2,5,3]
輸出：58
解釋：所有奇數(shù)長度子數(shù)組和它們的和為：
[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 個長度為奇數(shù)的子數(shù)組，[1] 和 [2]塞祈。它們的和為 3 办绝。
示例 3：
輸入：arr = [10,11,12]
輸出：66
題目分析：
- 求數(shù)組的連續(xù)數(shù)組
- 求數(shù)組的長度為奇數(shù)的連續(xù)子數(shù)組之和
思考：
先求出所有的連續(xù)子數(shù)組冒黑，然后再計算其中長度是基數(shù)的連續(xù)子數(shù)組之和试伙。
class Solution {
int total = 0;
int mark = 0;
int len;
int[] nums;
public int sumOddLengthSubarrays(int[] arr) {
nums = arr;
len = arr.length;
for (int i = 0; i < len; i++) {
dfs(len, i, new ArrayList<Integer>());
}
return total;
}
public void dfs(int len, int idx, ArrayList<Integer> list) {
if (idx == len) {
return;
}
mark++;
list.add(nums[idx]);
if (mark % 2 == 1) { // 判斷當(dāng)前子數(shù)組是否是奇數(shù)嘁信。
int sum = list.stream().reduce(Integer::sum).get();
total += sum;
}
dfs(len, idx + 1, list);
list.remove(Integer.valueOf(nums[idx]));
mark--;
}
}
