nums라는 숫자 목록과 두 개의 값 x와 y가 있다고 가정하고 길이가 x와 y인 숫자에서 겹치지 않는 두 하위 목록의 최대 합을 찾아야 합니다.
따라서 입력이 nums =[3, 2, 10, -2, 7, 6] x =3 y =1과 같으면 길이가 3인 하위 목록으로 [3, 2, 10] 그리고 다른 하나는 [7]을 선택합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- P :=단일 요소가 0인 목록
- A의 각 x에 대해 다음을 수행합니다.
- P 끝에 삽입(P + x의 마지막 요소)
- solve() 함수를 정의합니다. len1, len2가 필요합니다.
- Q :=범위 0에서 P - len1 크기까지의 각 i에 대한 요소(P[i + len1] - P[i])가 있는 목록
- 접두사 :=Q 사본
- 0에서 접두사 크기 - 1까지의 i에 대해
- 접두사[i + 1] :=접두사[i + 1] 및 접두사[i]의 최대값
- ans :=-무한대
- len1에서 P - len2까지의 범위에 있는 i에 대해
- left :=접두어[i - len1]
- 오른쪽 :=P[i + len2] - P[i]
- ans :=ans 및 (왼쪽 + 오른쪽)의 최대값
- 반환
- 메인 방법에서 다음을 수행하십시오 -
- solve(len1, len2) , solve(len2, len1)의 최대값 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution:
def solve(self, A, len1, len2):
P = [0]
for x in A:
P.append(P[-1] + x)
def solve(len1, len2):
Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]
prefix = Q[:]
for i in range(len(prefix) - 1):
prefix[i + 1] = max(prefix[i + 1], prefix[i])
ans = float("-inf")
for i in range(len1, len(P) - len2):
left = prefix[i - len1]
right = P[i + len2] - P[i]
ans = max(ans, left + right)
return ans
return max(solve(len1, len2), solve(len2, len1))
ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y)) 입력
[3, 2, 10, -2, 7, 6], 3, 1
출력
22