Python에서 동일한 합계의 3개의 겹치지 않는 하위 목록의 가장 큰 합계를 찾는 프로그램

<시간/>

nums라고 하는 숫자 목록과 또 다른 값 k가 있다고 가정하면 주어진 크기 k 목록의 겹치지 않는 세 하위 목록의 가장 큰 합을 찾아야 합니다.

따라서 입력이 nums =[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3] k =3과 같으면 출력은 27이 됩니다. 하위 목록 [2, 2, 2], [4, 4, 4] 및 [3, 3, 3], 총합은 27입니다.

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

P :=[0]
A의 각 x에 대해 다음을 수행합니다.
- P 끝에 P[-1] + x 삽입
Q :=[P[i + K] - P[i] for i in range 0 to size of P - K]
접두사 :=Q[인덱스 0에서 끝까지]
접미사 :=Q[인덱스 0에서 끝까지]
0에서 Q - 1의 크기 범위에 있는 i에 대해
- 접두사[i + 1] :=접두사[i + 1]의 최대값, 접두사[i]
- 접미사[~(i + 1) ] :=최대 접미사[~(i + 1) ], 접미사[~i]
ret =(Q[i] + 접두사[i - K] + 접미사[i + K]) 범위 K에서 Q - K - 1 크기의 각 i에 대해
ret의 최대값을 반환

예제(파이썬)

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

class Solution:
   def solve(self, A, K):
      P = [0]
      for x in A:
         P.append(P[-1] + x)
      Q = [P[i + K] - P[i] for i in range(len(P) - K)]
      prefix = Q[:]
      suffix = Q[:]
      for i in range(len(Q) - 1):
         prefix[i + 1] = max(prefix[i + 1], prefix[i])
         suffix[~(i + 1)] = max(suffix[~(i + 1)], suffix[~i])
      return max(Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K))
ob = Solution()
nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]
k = 3
print(ob.solve(nums, k))

입력

[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3