[Leetcode/Python] Maximum Subarray

Top Interview Questions 의 Easy Collection에 있는 문제입니다.      
문제는 여기서 볼 수 있습니다.

 

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

 

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 

Code:

from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # dp : 연속된 수의 마지막 인덱스가 i인 리스트
        dp = nums[:]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], nums[i] + dp[i-1])
        return max(dp)

tabulation방법으로 동적계획법 문제를 풀이하면 간단합니다.

숫자 리스트 nums의 길이만큼 for loop 를 돌면서, dp 리스트의 i번째 원소는 연속된 수의 리스트이면서 마지막 원소가 i번째 원소인 것 중에 그 리스트 내 원소의 합이 최대인 것이 들어가게 됩니다.