Python의 스택 목록에서 팝 된 k 요소의 최대 합을 찾는 프로그램

<시간/>

스택 목록과 정수 k가 있다고 가정합니다. 스택의 모든 조합에서 정확히 k개의 요소를 제거하여 얻을 수 있는 최대 합을 찾아야 합니다.

따라서 입력이 stack =[[50, -4, -15],[2],[6, 7, 8]], k =4와 같으면 출력은 39가 됩니다. 첫 번째 스택에서 3개의 요소를 제거하고 마지막 스택의 마지막 요소를 팝하여 -15 + -4 + 50 + 8 =39를 얻습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

함수 rec() 를 정의하십시오. 이것은 i, n
이 걸립니다.
n이 k와 같으면
- 0 반환
n> k이면
- 음의 무한대 반환
i가 스택 수와 같으면
- 음의 무한대 반환
i가 스택 수 - 1과 같으면
- 필요 :=k - n
- 필요한 경우> 스택의 요소 수[i], 다음
  - 음의 무한대 반환
- 그렇지 않으면
  - 스택[i] 마지막으로 필요한 요소 수
    의 요소 합계를 반환합니다.
res :=-math.inf, su :=0
스택의 범위 크기에 있는 sti의 경우[i] - 1에서 0,
1 감소, do
- su :=su + 스택[i, sti]
- localres :=su + rec(i + 1, n + 스택 크기[i] - sti)
- res :=res 및 localres의 최대값
res 및 rec(i + 1, n)의 최대값을 반환
메인 메소드 호출에서 rec(0, 0)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

import math

class Solution:
   def solve(self, stacks, k):
      def rec(i, n):
         if n == k:
            return 0
         if n > k:
            return -math.inf
         if i == len(stacks):
            return -math.inf
         if i == len(stacks) - 1:
            needed = k - n
            if needed > len(stacks[i]):
               return -math.inf
            else:
               return sum(stacks[i][-needed:])
         res, su = -math.inf, 0
         for sti in range(len(stacks[i]) - 1, -1, -1):
            su += stacks[i][sti]
            localres = su + rec(i + 1, n + len(stacks[i]) - sti)
            res = max(res, localres)
         return max(res, rec(i + 1, n))

      return rec(0, 0)

ob = Solution()
stacks = [
   [50, -4, -15],
   [2],
   [6, 7, 8]
]
k = 4
print(ob.solve(stacks, k))

입력

[[50, -4, -15],[2],[6, 7, 8]], 4