Maximum Nondecreasing Team Run
MediumDynamic Programming · Snowflake
You are given two integer arrays team_a and team_b of the same length n. Build a new array chosen of length n where, independently for each index i, chosen[i] is either team_a[i] or team_b[i].
Return the maximum length of a contiguous subarray of chosen that is non-decreasing (each element is greater than or equal to the one before it), over all possible ways of building chosen.
Example 1
- Input:
- team_a = [4, 1, 6, 2], team_b = [3, 5, 2, 7]
- Output:
- 4
- Explanation
- Choose
3(fromteam_b),5(team_b),6(team_a),7(team_b). The run[3, 5, 6, 7]covers all four positions.
Example 2
- Input:
- team_a = [9, 8, 7], team_b = [1, 10, 2]
- Output:
- 2
- Explanation
- Positions 0 and 1 work, e.g.
1, 8or9, 10. At position 2 both options, 7 and 2, are smaller than both options at position 1, so no run reaches length 3.
Example 3
- Input:
- team_a = [2, 2, 2], team_b = [2, 2, 2]
- Output:
- 3
- Explanation
- Non-decreasing allows equal neighbours, so the whole array
[2, 2, 2]counts.
Constraints
- 1 ≤
n==team_a.length==team_b.length≤ 105 - 1 ≤
team_a[i],team_b[i]≤ 109