Python에서 최대 합계로 인접한 하위 목록의 합계를 찾는 프로그램

배열 A가 있다고 가정합니다. 최대합이 있는 연속적인 하위 목록을 찾고 그 합도 반환해야 합니다. 따라서 배열 A가 A =[-2,1,-3,4,-1,2,1,-5,4]와 같으면 합계는 6이 됩니다. 그리고 하위 배열은 [4, -1, 2, 1].

이 문제를 해결하기 위해 동적 프로그래밍 방식을 사용하려고 합니다.

• A의 크기와 동일한 배열 dp를 정의하고 0으로 채웁니다.

• dp[0] :=A[0]

• for i :=1 ~ A – 1

  • dp[i] :=dp[i – 1] + A[i] 및 A[i]의 최대값

• 최대 dp를 반환

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

예시

class Solution(object):
   def solve(self, nums):
      dp = [0 for i in range(len(nums))]
      dp[0] = nums[0]
      for i in range(1,len(nums)):
         dp[i] = max(dp[i-1]+nums[i],nums[i])
      return max(dp)
nums = [-2,1,-3,7,-2,2,1,-5,4]
ob1 = Solution()
print(ob1.solve(nums))

입력

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

출력

8