Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr.

A subarray is a contiguous subsequence of the array.

&nbsp;
Example 1:

Input: arr = [1,4,2,5,3]
Output: 58
Explanation: The odd-length subarrays of arr and their sums are:
[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
If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:

Input: arr = [1,2]
Output: 3
Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12]
Output: 66


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 100
	1 &lt;= arr[i] &lt;= 1000


&nbsp;
Follow up:

Could you solve this problem in O(n) time complexity?

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        ans = 0
        for i in range(n):
            total = (i+1) * (n-1-i+1)
            ans = ans + (total//2 + total%2) * arr[i]
        return ans
class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        
        // Using two loops in this question...
        int sum = 0;
        for(int i=0 ; i<arr.length ; i++){
            int prevSum = 0;
            for(int j=i ; j<arr.length ; j++){
                prevSum+=arr[j];
                if((j-i+1)%2==1){
                    sum+=prevSum;
                }
            }
        }
        // Time Complexity : O(n-square)
        // Space Complexity : O(1)
        return sum;
    }
}
class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int sum=0;
        int sum1=0;
        for(int i=0;i<arr.size();i++)
        {
            int count=0;
            sum+=arr[i];
            for(int j=i;j<arr.size();j++)
            {
                sum1+=arr[j];
                count++;
                if(count%2!=0 and count!=1)
                    sum+=sum1;
            }
            sum1=0;
        }
        return sum;
    }
};
/*
Suppose N is the length of given array.
Number of subarrays including element arr[i] is
i * (N-i) + (N-i) because there are N-i subarrays with arr[i] as first element
and i * (N-i) subarrays with arr[i] as a not-first element. arr[i] appears in 
(N-i) subarrays for each preceding element and therefore we have i*(N-i).

Suppose i * (N-i) + (N-i) is `total`. Ceil(total / 2) is the number of odd-length subarrays and Floor(total / 2) is the number of even-length subarrays. 
When total is odd, there is one more odd-length subarray because of a single-element subarray.
    
For each number, we multiply its value with the total number of subarrays it appears and
add it to a sum.
*/
var sumOddLengthSubarrays = function(arr) {
    let sum = 0, N = arr.length;
    for (let i = 0; i < arr.length; i++) {
        let total = i * (N-i) + (N-i);
        sum += Math.ceil(total / 2) * arr[i];
    }
    return sum;
    // T.C: O(N)
    // S.C: O(1)
};
Sum of All Odd Length Subarrays