1588. Sum of All Odd Length Subarrays

Description

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.

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

Constraints:

1 <= arr.length <= 100
1 <= arr[i] <= 1000

Follow up:

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

Solutions

Solution 1: Dynamic Programming

We define two arrays \(f\) and \(g\) of length \(n\), where \(f[i]\) represents the sum of subarrays ending at \(\textit{arr}[i]\) with odd lengths, and \(g[i]\) represents the sum of subarrays ending at \(\textit{arr}[i]\) with even lengths. Initially, \(f[0] = \textit{arr}[0]\), and \(g[0] = 0\). The answer is \(\sum_{i=0}^{n-1} f[i]\).

When \(i > 0\), consider how \(f[i]\) and \(g[i]\) transition:

For the state \(f[i]\), the element \(\textit{arr}[i]\) can form an odd-length subarray with the previous \(g[i-1]\). The number of such subarrays is \((i / 2) + 1\), so \(f[i] = g[i-1] + \textit{arr}[i] \times ((i / 2) + 1)\).

For the state \(g[i]\), when \(i = 0\), there are no even-length subarrays, so \(g[0] = 0\). When \(i > 0\), the element \(\textit{arr}[i]\) can form an even-length subarray with the previous \(f[i-1]\). The number of such subarrays is \((i + 1) / 2\), so \(g[i] = f[i-1] + \textit{arr}[i] \times ((i + 1) / 2)\).

The final answer is \(\sum_{i=0}^{n-1} f[i]\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(\textit{arr}\).

Python3JavaC++GoTypeScriptRustC

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

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;
    }
}

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int n = arr.size();
        vector<int> f(n, arr[0]);
        vector<int> g(n);
        int ans = f[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;
    }
};

func sumOddLengthSubarrays(arr []int) (ans int) {
    n := len(arr)
    f := make([]int, n)
    g := make([]int, n)
    f[0] = arr[0]
    ans = f[0]
    for 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
}

function sumOddLengthSubarrays(arr: number[]): number {
    const n = arr.length;
    const f: number[] = Array(n).fill(arr[0]);
    const g: number[] = Array(n).fill(0);
    let ans = f[0];
    for (let i = 1; i < n; ++i) {
        f[i] = g[i - 1] + arr[i] * ((i >> 1) + 1);
        g[i] = f[i - 1] + arr[i] * ((i + 1) >> 1);
        ans += f[i];
    }
    return ans;
}

impl Solution {
    pub fn sum_odd_length_subarrays(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut f = vec![0; n];
        let mut g = vec![0; n];
        let mut ans = arr[0];
        f[0] = arr[0];
        for i in 1..n {
            f[i] = g[i - 1] + arr[i] * ((i as i32) / 2 + 1);
            g[i] = f[i - 1] + arr[i] * (((i + 1) as i32) / 2);
            ans += f[i];
        }
        ans
    }
}

int sumOddLengthSubarrays(int* arr, int arrSize) {
    int n = arrSize;
    int f[n];
    int g[n];
    int ans = f[0] = arr[0];
    g[0] = 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;
}

Solution 2: Dynamic Programming (Space Optimization)

We notice that the values of \(f[i]\) and \(g[i]\) only depend on \(f[i - 1]\) and \(g[i - 1]\). Therefore, we can use two variables \(f\) and \(g\) to record the values of \(f[i - 1]\) and \(g[i - 1]\), respectively, thus optimizing the space complexity.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\).