力扣 1588. 所有奇数长度子数组的和

题目来源：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/

大致题意：
给出一个数组，求出其所有奇数长度子序列的和

思路

找规律

每个数在奇数长度子序列中出现的次数是有规律的。
我尝试用数列解但是失败了。

1. 对于每个元素本身来说，就是一个长度为 1 的奇数长度子序列，然后它能加入奇数个其它元素形成新的子序列。并且其要与加入的元素连续。
2. 那么假定当前元素的下表为 i，那么其左边有 i 个元素，右边有 n-1-i 个元素。由于我们可以选择某一边不加元素，于是，左边可供选择的元素数量组合有 i+1 种，右边有 n-i 种。
3. 接下来考虑，若左边加入加入奇数个元素，那么右边必须也加入奇数个元素，这样加上元素本身才能构成奇数长度子序列；同理，左边偶数个元素，右边也需要偶数个元素。那么，在上面提出的条件下，左边选出奇数个元素的种类有 (i+1) / 2 种，右边为 (n-i) / 2 种，左边选出偶数个元素的种类有 [(i+1) + 1] / 2种，右边有 [(n-i)+1] / 2 种。
4. 将两边能构成的种类计算出，再乘上元素值本身，即构成了该元素对最终和的贡献值。统计所有元素的贡献值，即可。

代码为：

public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 左边可供选择的数的个数
            int left = i + 1;
            // 右边可供选择的数的个数
            int right = n - i;
            // 左边构成偶数个元素的选择个数 0 2 4 8...
            int left_even = (left + 1) / 2;
            // 左边构成奇数个元素的选择个数 1 3 5 7...
            int left_odd = left / 2;
            // 右边
            int right_even = (right + 1) / 2;
            int right_odd = right / 2;
            // 左边的种类个数 * 右边的种类个数 即为 当前元素会出现的不同奇数子序列的种类个数
            // 乘上当前元素值本身
            ans += (left_even*right_even + left_odd * right_odd) * arr[i];
        }
        
        return ans;
    }