[LeetCode] 53. Maximum Subarray - 파이썬(Python)

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

Maximum Subarray - LeetCode

유형 : 동적 계획법(Dynamic Programming)

문제 설명

정수 배열 nums가 주어지면, 가장 큰 합을 갖는 연속적인 하위 배열(최소한 하나의 숫자를 포함)을 찾아 return 하는 문제이다. 하위 배열은 배열의 연속적인 부분이다.

Example 1)
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1]이 가장 큰 합을 값는 하위 배열이다.

Example 2)
Input: nums = [1]
Output: 1

Example 3)
Input: nums = [5,4,-1,7,8]
Output: 23

제한사항

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

문제 풀이

성공 코드

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        
        if len(nums) == 1:
            return nums[0]
        
        dp_array = [0] * len(nums)
        dp_array[0] = nums[0]
        
        for idx in range(1,len(nums)):
            prev_max = dp_array[idx-1]
            crnt_val = nums[idx]
            
            connected_sum = prev_max + crnt_val
            max_sub = max(connected_sum , crnt_val)
            dp_array[idx] = max_sub
            
        max_sum = max(dp_array)
        return max_sum

시간 복잡도 : O(n)

n은 nums의 크기이다.

공간 복잡도 : O(n)

n은 nums의 크기이다.