number-of-sub-arrays-with-odd-sum

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an array of integers <code>arr</code>, return the number of subarrays with an odd sum.

Since the answer can be very large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<pre>
Input: arr = [1,3,5]
Output: 4
Explanation: All subarrays 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.
</pre>

Example 2:

<pre>
Input: arr = [2,4,6]
Output: 0
Explanation: All subarrays 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.
</pre>

Example 3:

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

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= arr.length &lt;= 105</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 100</code></li>
</ul>

numOfSubarrays

Number of Sub-arrays With Odd Sum

Subsequence of Size K With the Largest Even Sum

subsequence-of-size-k-with-the-largest-even-sum

长度为 K 的最大偶数和子序列

Array

Math

Dynamic Programming

Prefix Sum

给你一个整数数组&nbsp;<code>arr</code>&nbsp;。请你返回和为 奇数&nbsp;的子数组数目。

由于答案可能会很大，请你将结果对&nbsp;<code>10^9 + 7</code>&nbsp;取余后返回。

&nbsp;

示例 1：

<pre>输入：arr = [1,3,5]
输出：4
解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
所有子数组的和为 [1,4,9,3,8,5].
奇数和包括 [1,9,3,5] ，所以答案为 4 。
</pre>

示例 2 ：

<pre>输入：arr = [2,4,6]
输出：0
解释：所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
所有子数组和为 [2,6,12,4,10,6] 。
所有子数组和都是偶数，所以答案为 0 。
</pre>

示例 3：

<pre>输入：arr = [1,2,3,4,5,6,7]
输出：16
</pre>

示例 4：

<pre>输入：arr = [100,100,99,99]
输出：4
</pre>

示例 5：

<pre>输入：arr = [7]
输出：1
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= arr.length &lt;= 10^5</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 100</code></li>
</ul>