정수 배열 A가 있다고 가정합니다. 길이가 최소 1이고 합이 가장 큰 연속 하위 배열을 찾고 합도 반환해야 합니다. 따라서 배열 A가 A =[-2,1,-3,4,-1,2,1,-5,4]와 같으면 합계는 6이 됩니다. 그리고 하위 배열은 [4, -1 , 2, 1]
이 문제를 해결하기 위해 동적 프로그래밍 방식을 사용하려고 합니다.
- A의 크기와 같은 배열 dp를 정의하고 0으로 채웁니다.
- dp[0] :=A[0]
- i =1의 경우 A – 1의 크기
- dp[i] :=dp[i – 1] + A[i] 및 A[i]의 최대값
- 최대 dp를 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
예제(파이썬)
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ 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]) #print(dp) return max(dp) nums = [-2,1,-3,7,-2,2,1,-5,4] ob1 = Solution() print(ob1.maxSubArray(nums))
입력
nums = [-2,1,-3,7,-2,2,1,-5,4]
출력
8