오늘도 달린닷 DP 잡으러 🏃‍♀️

53. Maximum Subarray

description

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

Example:

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

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.

Solution

Code

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        contiguous = [0] * len(nums)
        contiguous[0] = nums[0]
        
        for i in range(1, len(nums)) :
            contiguous[i] = max(contiguous[i-1]+nums[i], nums[i])
            
        return max(contiguous)

Logic

가장 큰 합이 나올 수 있는 연속적인 수들을 찾는 문제였다. 물론 더 빨리 답을 찾으려면 maximum에 대한 변수를 선언하면 되겠지만? 일단 나는 선언하지 않고 배열의 가장 큰 값을 리턴하게끔 코드를 짰다. i번째 num을 포함하는 최대의 연속적인 합은 i-1번까지의 최대 + nums[i] 값 또는 nums[i] 자체 일 것이다. (즉 nums[i]부터 다시 시작)

인덱스 0은 무조건 nums[0]이므로 선언하고 이후 1부터 nums의 길이 - 1까지 순회하면서 dp 알고리즘을 이용했다.

문제 링크

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