Given an array of integers arr. Return the number of sub-arrays with odd sum.

As the answer may grow large, the answer must be computed modulo 10^9 + 7.

 

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.

Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16

Example 4:

Input: arr = [100,100,99,99]
Output: 4

Example 5:

Input: arr = [7]
Output: 1

 

Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 100

方法：dp

思路：

1 可以形成奇数和的情况只有两种，一种是之前的和是偶数，加入一个奇数。或者是之前的和是奇书，加入一个偶数。

2 所以我们可以维护两个数组，分别记录在遇到这个数字之前的偶数和的情况以及奇数和的情况。(dp_ones[i], dp_zeros[i])

3 如果当前我们遇到的这个数字是偶数，那么dp_ones[i] = 1 + dp_ones[i-1]如果遇到的数字是奇书，dp_ones[i] = 1 + dp_zeros[i-1]

4 最后的答案是dp_ones数组加和

time complexity O(n) space complexity O(n)

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        if not arr or len(arr) == 0: return 0 
        mod = 1e9 + 7
        arr2 = [a % 2 for a in arr]
        
        n = len(arr2)
       
        dp_ones = [0] * n
        dp_zeros = [0] * n
        
        if arr2[0] == 1:
            dp_ones[0] = 1 
        else:
            dp_zeros[0] = 1 
            
        for i in range(1, n):
            if arr2[i] == 1:
                dp_ones[i] = 1 + dp_zeros[i-1]
                dp_ones[i] %= mod 
                dp_zeros[i] = dp_ones[i-1]
            else:
                dp_ones[i] = dp_ones[i-1]
                dp_zeros[i] = 1 + dp_zeros[i-1]
                dp_zeros[i] %= mod 
     
        res = 0 
        for d in dp_ones:
            res += d 
            res %= mod 
            
        return int(res)