nums라는 배열이 있다고 가정하고 이 배열을 nums로 분할하는 좋은 방법의 수를 찾아야 합니다. 응답이 너무 클 수 있으므로 모듈로 10^9 + 7을 반환합니다. 여기서 배열의 분할(정수 요소 포함)은 배열이 왼쪽에서 오른쪽으로 각각 비어 있지 않은 세 개의 연속 하위 배열로 분할되고 왼쪽 요소의 합은 중간 요소의 합보다 작거나 같고, 중간 요소의 합은 오른쪽 요소의 합보다 작거나 같습니다.
따라서 입력이 nums =[2,3,3,3,7,1]과 같으면 세 가지 분할 방법이 있으므로 출력은 3이 됩니다.
- [2],[3],[3,3,7,1]
- [2],[3,3],[3,7,1]
- [2,3],[3,3],[7,1]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=숫자 크기,
- m :=10^9+7
- ss :=크기(1+n)의 배열이고 0으로 채워짐
- nums의 각 인덱스 i 및 값 val에 대해 수행
- ss[i] :=ss[i-1] + 발
- r :=0, rr :=0, ans :=0
- 1~n-2 범위의 l에 대해 다음을 수행합니다.
- r :=r 및 l+1의 최대값
- r
- r :=r + 1
- rr :=rr 및 r의 최대값
- rr
=ss[rr+1] - ss[l]인 동안 do - rr :=rr + 1
- ss[l]> ss[r] - ss[l]이면
- 루프에서 나오다
- ss[r] - ss[l]> ss[n] - ss[r]이면
- 다음 반복으로 이동
- ans :=(ans + rr - r + 1) 모드 m
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums): n, m = len(nums), 10**9+7 ss = [0] * (1+n) for i, val in enumerate(nums, 1): ss[i] = ss[i-1] + val r = rr = ans = 0 for l in range(1, n-1): r = max(r, l+1) while r < n-1 and ss[r]-ss[l] < ss[l]: r += 1 rr = max(rr, r) while rr < n-1 and ss[n]-ss[rr+1] >= ss[rr+1]-ss[l]: rr += 1 if ss[l] > ss[r]-ss[l]: break if ss[r]-ss[l] > ss[n]-ss[r]: continue ans = (ans+rr-r+1) % m return ans nums = [2,3,3,3,7,1] print(solve(nums))
입력
[1,7,3,6,5]
출력
3