LeetCode #53

Maximum Subarray

1개의 풀이 · Python

SOLUTION INFO

Python · main.py

작성자: tony9402
공동 작성자: 없음
링크: 제출 보기 ↗ GitHub 원본 ↗

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -10000
        S = 0
        for x in nums:
            S = max(x, S + x)
            ans = max(ans, S)
        return ans

SOLUTION DESCRIPTION

풀이 설명

해당 알고리즘은 매우 유명한 알고리즘이다. 카데인 알고리즘 (kadane algorithm) DP 방식으로 풀었으며 아래와 같이 점화식을 구할 수 있다. DP[i]: 연속된 부분 수열 중 i번째 원소로 끝나는 수열의 합 중 최대인 값 if i == 0 : DP[i] = nums[0] else : DP[i] = max(nums[i], nums[i] + DP[i - 1])

GITHUB COMMUNITY

커뮤니티 평가

GitHub 계정으로 남긴 최신 평가 1건만 반영하며, 데이터는 매일 저장소에 동기화됩니다.

최근 동기화 2026-08-21T15:51:10Z

체감 난이도

아직 평가 없음

첫 난이도 평가를 남겨주세요.

문제 추천

아직 평가 없음

이 문제가 도움이 되었는지 알려주세요.

이 문제 평가하기

GitHub 로그인 후 난이도를 제출하고, 원하는 경우 추천 여부도 함께 남길 수 있습니다.

체감 난이도