문제 : Maximum Subarray
문제 설명
정수 배열의 nums가 주어졌을 때,
합이 가장 큰 연속적인 하위 배열(하나 이상의 숫자를 포함)을 찾아 그 합을 반환합니다.
하위 배열은 배열의 연속적인 부분입니다.
문제 풀이
이 문제의 관련 주제입니다
Related Topic - Array/Divide and Conquer/Dynamic Programming
저는 Dynamic Programming 동적 프로그래밍을 사용하여 이 문제를 풀었습니다.
다이내믹 프로그래밍 알고리즘이란?
문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가
나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘입니다.
이 문제에 동적 프로그래밍 알고리즘을 적용한다면 배열을 한 번만 확인하면서
현재 값과 현재 값+ 이전 값을 합친 값 중 비교해 더 큰 값을 현재 인덱스에 저장합니다.
현재 값이 더 크면 이전 까지의 하위 배열을 포기하고 다른 하위 배열을 시작하는 것이고현재 값에 이전 값을 더한 값이 더 크다면 하위 배열이 현재 값까지 확장되고 그 하위 배열의 합이 현재 인덱스에 저장됩니다.
전채 배열에서 하위 배열의 합 중 가장 큰 갑을 찾는 문제를 현재 값과 현재 값+이전 값을 비교하는 작은 문제로 나누어 해결한 값을 저장하여 큰 문제를 푸는 방식입니다.
<그림으로 이해하기>
아래는 문제 해결 과정을 그림으로 나타낸 것입니다.
만약 [-2,1,-3,4,-1,2,1,-5,4] 입력된다면
결과는 [4,-1,2,1] 하위 배열의 합 6이 반환되어야 합니다.
첫 번째는 이전 값이 없기 때문에 건너뛰고 두 번째 값부터 확인합니다.
[-2,1] 보다 [1]
현재 값은 1이고 현재 값에 이전 값을 더한 값은 -1로
[-2,1] 보다 [1]에서 하위 배열을 확장하지 않는 것[1]이 이득이므로
현재 값만 저장합니다.
현재 값인 -3 보다 현재 값에 이전 값인 -1을 더한 것이 더 크므로 하위 배열을 확장하고 그 합을 현재 인덱스에 저장합니다. 이와 같은 과정을 배열의 마지막 값까지 반복하면서 반환할 최댓값을 갱신하면서 저장해줍니다.
이렇게 마지막 값까지 반복이 끝날을 때 최댓값을 반환해주면 됩니다.
아래의 빨간 리스트는 입력 리스트에 하위 배열이 어떻게 나누어졌는지 표시한 것입니다.
<Pseudo code>
파이썬으로 작성한 코드입니다.
<Python 코드>
class Solution(object):
def maxSubArray(self, nums):
max_num = nums[0]
for i in range(1, len(nums)):
if nums[i-1] + nums[i] > nums[i]:
nums[i] += nums[i-1]
if max_num < nums[i]:
max_num = nums[i]
return max_num