동적 계획법 연습(bottom-up) - 최대서브배열(leetcode)

문제:https://leetcode.com/problems/maximum-subarray/

손계획

코드

class Solution:
    def maxSubArray(self, nums) -> int:
        # 각 인덱스의 숫자를 끝점으로 하는 배열들 중 최대합을 적어가기 위한 기록 테이블
        n = len(nums)
        record = [0] * n
        record[0] = nums[0]

        for i in range(1, n):
            # 이전칸까지의 최대합이 음수면 이전의 정보는 반영 안하고 자신만을 반영
            if record[i-1] < 0:
                record[i] = nums[i]
            # 이전칸까지 최대합이 양수면 더하는 게 무조건 나으므로 반영하여 자신도 추가
            else:
                record[i] = record[i-1] + nums[i]

        return max(record)

궁금한 점

리트코드에 이렇게 안내가 되어 있었다. 분할 정복 접근을 사용하는 다른 해결책도 찾아보라고 하는데 어떤 것일지 궁금하다..!