LeetCode : Maximum Subarray (Easy)

0. Overview

• 풀이 날짜 : 2021-06-18
• 풀이 소요 시간 : 40m
• LeetCode URL : https://leetcode.com/problems/maximum-subarray/

1. Problem

2. Solution

def maxSubArray(nums: List[int]) -> int:    
    candidates = [n for n in nums]
    
    for i in range(1, len(nums)) :
        candidates[i] = max(candidates[i-1] + nums[i], nums[i])
    return max(candidates)

3. Review

• 연속되는 수의 최대 합을 구하는 문제로, Dynamic Programming 방식으로 i번째 원소에 대해 (1) 현재까지의 누적값과 (2) i번째 원소 + 누적값을 비교하여 더 큰 값을 누적값으로 대체하는 방식으로 최대 합을 구할 수 있습니다.
• 위 코드에서 리스트 candidates 를 리스트 nums 로 초기화 하고, candidates[i] = max(candidates[i-1] + nums[i], nums[i]) 부분을 통해 i 번째 원소까지 최대 누적 합을 candidates[i] 내에 갱신+저장합니다.
• 전체 누적합 중에 가장 큰 값을 리턴함으로써 원하는 답을 얻을 수 있습니다.