Maximum Subarray

[Leetcode] 53 - Maximum Subbaray

내가 좋아하는 DP유형의 문제이다. 문제 접근법이 어려운편은 아니어서 쉽게 풀렸다.
이 문제의 요구사항은 합이 가장 큰 연속된 수의 배열을 찾는것이다.
DP는 일반적으로 반복되는 계산을 최소화하므로써 구현이 가능한데
주어진 예시를 살펴보자.

단순하게 바로 무작정 풀 수 있는 방법을 떠올리라고 한다면, 배열의 요소 하나하나 마다 리스트 전체를 순회하며 찾으면 답은 나올것이다. 시간이 오래걸려서 그렇지
문제에서 요구되는것은 결국 합이 가장 큰 연속된 수의 배열이므로 가장 큰 값을 저장해 나가면서 계산하면 최소화 할 수 있을것이다.
코드를 살펴보자.

def maxSubArray(self, nums):
        L = len(nums)
        DP = [0] * L
        for i in range(L):
            DP[i] = max(nums[i], nums[i] + DP[i - 1])
        return max(DP)

위는 처음에 짠 코드인데 DP라는 배열을 미리 nums배열의 크기만큼 만들어주고
현재 검사하는 nums[i]의 값과 nums[i] + DP[i - 1]을 비교해준다.

만약 nums[i] + DP[i - 1]가 더 크다면
이전에 구했던 최댓값과 현재의 값을 더한 결과를 DP[i]에 저장해준다.

반대로 nums[i]가 더 크다면 이전의 최댓값이 음수라서 더해도 값이 더 작아지므로
DP[i]에 nums[i]를 저장한다.

근데 짜고보니 굳이 DP라는 배열을 만들 필요없이 바로 nums 배열에 바로바로 적용시켜도 문제없을 것 같아서 더 간단하게 수정했다.

def maxSubArray(self, nums):
        for i in range(1, len(nums)):
            nums[i] = max(nums[i], nums[i] + nums[i - 1])
        return max(nums)

주어진 예시로 흐름을 살펴보겠다.
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

• i == 1 일 때
  nums[1] = 1, nums[0] = -2 이므로
  nums[1] > nums[1] + nums[0]이 된다.
  따라서 nums[1] 에는 값 변화없이 그대로 유지
  nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

• i == 2 일 때
  nums[2] = -3, nums[1] = 1 이므로
  nums[2] < nums[2] + nums[1]이 된다.
  따라서 nums[2] 에는 nums[2] + nums[1] = -2인 -2를 저장한다.
  nums = [-2, 1, -2, 4, -1, 2, 1, -5, 4]

• i == 3 일 때
  nums[3] = 4, nums[2] = -2 이므로
  nums[3] > nums[3] + nums[2]이 된다.
  따라서 nums[3] 에는 값 변화없이 그대로 유지
  nums = [-2, 1, -2, 4, -1, 2, 1, -5, 4]

• i == 4 일 때
  nums[4] = -1, nums[3] = 4 이므로
  nums[4] < nums[4] + nums[3]이 된다.
  따라서 nums[4] 에는 nums[4] + nums[3] = 3인 3을 저장한다.
  nums = [-2, 1, -2, 4, 3, 2, 1, -5, 4]

• i == 5 일 때
  nums[5] = 2, nums[4] = 3 이므로
  nums[5] < nums[5] + nums[4]이 된다.
  따라서 nums[5] 에는 nums[5] + nums[4] = 5인 5을 저장한다.
  nums = [-2, 1, -2, 4, 3, 5, 1, -5, 4]

• i == 6 일 때
  nums[6] = 1, nums[5] = 5 이므로
  nums[6] < nums[6] + nums[5]이 된다.
  따라서 nums[6] 에는 nums[6] + nums[5] = 6인 6을 저장한다.
  nums = [-2, 1, -2, 4, 3, 5, 6, -5, 4]

• i == 7 일 때
  nums[7] = -5, nums[6] = 6 이므로
  nums[7] < nums[7] + nums[6]이 된다.
  따라서 nums[7] 에는 nums[7] + nums[6] = 1인 1을 저장한다.
  nums = [-2, 1, -2, 4, 3, 5, 6, 1, 4]

• i == 8 일 때
  nums[8] = -5, nums[7] = 6 이므로
  nums[8] < nums[8] + nums[7]이 된다.
  따라서 nums[8] 에는 nums[8] + nums[7] = 5인 5을 저장한다.
  nums = [-2, 1, -2, 4, 3, 5, 6, 1, 5]

이렇게 완성된 배열에서 가장 큰 값을 찾아서 반환하기만 하면 정답을 제출할 수 있다.

흐름에서 살펴볼 수 있는것은 최댓값을 저장을 하되, 현재 더하려는 값과 비교하여
현재값 > 현재값 + 최댓값 일 때 최댓값을 현재값으로 초기화하고 다시 더해간다.
현재값 < 현재값 + 최댓값 이면 기존의 최댓값에 현재값을 더하고 저장한다.