숨겨진 시퀀스 계산

n 정수 differences 의 인덱스가 0인 배열이 주어집니다. 이 배열은 길이가 (n + 1) 인 숨겨진 시퀀스의 각 연속 정수 쌍 간의 차이를 설명합니다. 더 공식적으로 숨겨진 시퀀스를 hidden라고 부르면 differences[i] = hidden[i + 1] - hidden[i]가 됩니다.

또한 히든 시퀀스가 ​​포함할 수 있는 값의 범위lower를 설명하는 두 개의 정수upper 및 [lower, upper]가 제공됩니다.

예를 들어, 주어진 differences = [1, -3, 4] , lower = 1 , upper = 6 에서 히든 시퀀스는 요소가 4와 1(포함) 사이에 있는 길이가 6인 시퀀스입니다.

[3, 4, 1, 5] 및 [4, 5, 2, 6]는 가능한 숨겨진 시퀀스입니다.

[5, 6, 3, 7]는 6보다 큰 요소를 포함하므로 불가능합니다.

[1, 2, 3, 4] 차이가 올바르지 않기 때문에 불가능합니다.

가능한 히든 시퀀스의 수를 반환합니다. 가능한 시퀀스가 ​​없으면 0 를 반환합니다.

예 1:

입력: 차이 = [1,-3,4], 하위 = 1, 상위 = 6
출력: 2
설명: 가능한 숨겨진 시퀀스는 다음과 같습니다.

[3,4,1,5]

[4, 5, 2, 6]
따라서 2를 반환합니다.

예 2:

입력: 차이 = [3,-4,5,1,-2], 하위 = -4, 상위 = 5
출력: 4
설명: 가능한 숨겨진 시퀀스는 다음과 같습니다.

[-3, 0, -4, 1, 2, 0]

[-2, 1, -3, 2, 3, 1]

[-1, 2, -2, 3, 4, 2]

[0, 3, -1, 4, 5, 3]
따라서 4를 반환합니다.

예 3:

입력: 차이 = [4,-7,2], 하위 = 3, 상위 = 6
출력: 0
설명: 가능한 숨겨진 시퀀스가 ​​없습니다. 따라서 0을 반환합니다.

제약:

n == differences.length

1 <= n <= 105

-105 <= differences[i] <= 105

-105 <= lower <= upper <= 105

해결책:

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        pos = [0]
        for d in differences:
            pos.append(pos[-1] + d)
        least = min(pos)
        pos = [p + lower - least for p in pos]
        return max(upper - max(pos) + 1, 0)