Python에서 가장 큰 K 하위 목록의 합을 찾는 프로그램

nums라는 숫자 목록과 k번 연결된 숫자의 큰 목록을 나타내는 또 다른 값 k가 있다고 가정합니다. 가장 큰 합을 가진 인접한 하위 목록의 합을 찾아야 합니다.

따라서 입력이 nums =[1, 3, 4, -5], k =1과 같으면 출력은 [2, 4, 5]

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

• s :=ans :=lo :=0
• 0에서 k와 2의 최소값 범위에 있는 모든 값에 대해 다음을 수행합니다.
  • 숫자 단위의 각 x에 대해 다음을 수행합니다.
    • s :=s + x
    • lo :=lo의 최소값, s
    • ans :=최대 ans, s - lo
• 반환 ans + 최대값 0 및 nums의 모든 요소의 합 * 최대값 0 및 (k - 2)

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

예시

class Solution:
   def solve(self, nums, k):
      s = ans = lo = 0
      for _ in range(min(k, 2)):
         for x in nums:
            s += x
            lo = min(lo, s)
         ans = max(ans, s - lo)
      return ans + max(0, sum(nums)) * max(0, (k - 2))
ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

입력

[2, 4, 5, -4], 1

출력

11