항해99, 5주차 최대 서브 배열

Today I learned
2022/02/09

회고록

2/09

항해 99, 알고리즘 4주차(항해 5주차)

교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)

다이나믹 프로그래밍

1. 이론

이론 정리 포스팅 글(내 벨로그)

https://velog.io/@jsw4215/%ED%95%AD%ED%95%B499-5%EC%A3%BC%EC%B0%A8-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D

2. 문제

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.

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

3. MySol

• DP btm-up memoization

nums = [-2,1,-3,4,-1,2,1,-5,4]

d = [0]*len(nums)

d[0] = -2
d[1] = 1

for i in range(2, len(nums)):
    if d[i-1] <= 0:
        d[i] = nums[i]
    else:
        d[i] = nums[i] + d[i-1]

print(f'{max(d)}')

4. 배운 점

• DP
• 바텀업 방식으로 메모이제이션 구현

5. 총평

DP 알고리즘 익히기