[Python]동적계획법 백준 1912

   문제

   https://www.acmicpc.net/problem/1912

다시 수열 문제로 돌아왔다.

현재수를 포함하는 연속된 수의 합이 최대가 되는경우는 두가지이다.

현재수와 이전까지 연결된 합의 최대를 더한 값 또는 이번 수만 선택했을때의 값이다.

다음수도 같은방법으로 수열의 끝까지 반복해준다.

각 숫자까지의 합이 최대가 되는수중 최댓값을 구해준다.

import sys
 
 
n=int(sys.stdin.readline())
num_list=list(map(int,sys.stdin.readline().split()))
result=[0 for _ in range(n)]
 
def continueSum(n):
    result[0]=num_list[0]
    if n==1:
        return
    for i in range(n):#각 단계에서 골랐을때의 최대값을 구한다.
        result[i]=max(num_list[i],num_list[i]+result[i-1])
 
 
continueSum(n)
print(max(result))