[Leetcode] 53. Maximum Subarray

Jonghae Park·2021년 11월 25일
0

영혼의 알고리즘

목록 보기
6/19

21-11-25
unsolved

Problems

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.

Solution

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l=len(nums)
        if l==1:
            return nums[0]
        dp=[0]*l#0th:
        dp[0]=nums[0]
        maxNum=dp[0]
        for i in range(1,l):
            dp[i]=max(nums[i],nums[i]+dp[i-1])
            if maxNum<dp[i]:
                maxNum=dp[i]
            
        return maxNum

옛날에 백준에서 풀어놓고 까먹어서 못 풀었다.
찾아보니, 해당 문제를 해결하는 알고리즘이 잘 알려져있었다.

Kadane's Algorithm

최대합 부분수열 구하는 알고리즘. O(N)

Dynamic Programming - 어떤 문제를 해결 가능한 하위 문제로 나누어 푸는 방법.

dp[i]: i번째 원소를 마지막으로 하는 subarray의 최대합.
이 때 다음과 같은 점화식이 성립한다.

dp[i]=max(nums[i],nums[i]+dp[i-1])

말로 한 번 더 정리해보자.

i번째 원소를 마지막으로 하는 최대합을 가진 subarray를 구하려면,
1) i-1번째 원소를 마지막으로 하는 최대합 subarry에다가 i번째 원소를 더하거나
2) i 번째 원소로만 subarray를 만들거나
두 가지 경우 밖에 없다.

이런 알고리즘은 그냥 기억해야하나 싶다.

profile
알고리즘 정리 좀 해볼라고

0개의 댓글