[Python/코테] 백준 1912 연속합

1912 연속

문제 및 조건 설명: https://www.acmicpc.net/problem/1912

알고리즘 설계

1. 테이블 정의하기

D[i] = i번째 원소까지의 최대합

D[i][j] = i부터 j까지 숫자의 합. 항상 i ≤ j ≤ n

 

2. 점화식 설정하기

D[i] = max(d[i-1]+arr[i], arr[i])

D[i][k] = D[i][j-1] + arr[i+j]

 

3. 최소값 정의하기

D[0] = arr[0]

D[i][1] = i

알고리즘 구현

출처: https://lemon27.tistory.com/10

import sys

n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().split()))
d = [0] * n
d[0] = arr[0]

for i in range(1, n):
    d[i] = max(arr[i], d[i-1]+arr[i])

print(max(d))

나다어

• 테이블은 활용되어야 한다.
  답을 구하기 위해 활용할 수 있는 형태 + 케이스를 쪼개서 생각할 수 있는 형태로 테이블을 정의한다.
• 이 문제에서는 '합'을 구하는 문제이므로, 매번 다시 합 연산을 하는 것은 불필요하다. → 이 단서를 활용해서 테이블 고안하기!