1588. Sum of All Odd Length Subarrays

Problem Description:

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays of arr. A subarray is a contiguous subsequence of the array.

Approach 1: Dynamic Programming

This approach uses dynamic programming to efficiently calculate the sum. We define two arrays:

• f[i]: The sum of odd-length subarrays ending at index i.
• g[i]: The sum of even-length subarrays ending at index i.

The recurrence relations are:

• f[i] = g[i-1] + arr[i] * ((i+1)/2) (for i > 0)
• g[i] = f[i-1] + arr[i] * (i/2) (for i > 0)

The base cases are f[0] = arr[0] and g[0] = 0. The final answer is the sum of all f[i] values.

Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.

Space Complexity: O(n), due to the f and g arrays.

Approach 2: Dynamic Programming with Space Optimization

We observe that we only need the previous values of f and g to calculate the current values. Thus, we can optimize space complexity to O(1) by using only two variables to store these previous values.

Time Complexity: O(n)

Space Complexity: O(1)

Code Implementation (Python):

Approach 1:

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        n = len(arr)
        f = [0] * n
        g = [0] * n
        ans = f[0] = arr[0]
        for i in range(1, n):
            f[i] = g[i - 1] + arr[i] * (i // 2 + 1)
            g[i] = f[i - 1] + arr[i] * ((i + 1) // 2)
            ans += f[i]
        return ans
 

Approach 2:

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        ans, f, g = arr[0], arr[0], 0
        for i in range(1, len(arr)):
            ff = g + arr[i] * (i // 2 + 1)
            gg = f + arr[i] * ((i + 1) // 2)
            f, g = ff, gg
            ans += f
        return ans

Code Implementation (Java): (Similar structure for other languages)

Approach 1:

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int[] f = new int[n];
        int[] g = new int[n];
        int ans = f[0] = arr[0];
        for (int i = 1; i < n; ++i) {
            f[i] = g[i - 1] + arr[i] * (i / 2 + 1);
            g[i] = f[i - 1] + arr[i] * ((i + 1) / 2);
            ans += f[i];
        }
        return ans;
    }
}

Approach 2:

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int ans = arr[0], f = arr[0], g = 0;
        for (int i = 1; i < arr.length; ++i) {
            int ff = g + arr[i] * (i / 2 + 1);
            int gg = f + arr[i] * ((i + 1) / 2);
            f = ff;
            g = gg;
            ans += f;
        }
        return ans;
    }
}

The code implementations in other languages (C++, Go, TypeScript, Rust, C) would follow a very similar structure to the Java examples, reflecting the same dynamic programming logic. The key differences would lie primarily in syntax and data structure handling.