연속합 [백준 1912] - python

import sys
input = sys.stdin.readline

def BOJ1912() :
  n = int(input())
  l = list(map(int, input().split()))
  dp = list(l)
  for i in range(1, n) :
    dp[i] = max(dp[i-1] + l[i], l[i])

  print(max(dp))

BOJ1912()

 

1. 연속된 숫자들의 합중 최댓값을 구하면 된다. 이전 까지의 합을 이용해야 하므로 dp를 적용하였다.

2. 수를 한 개이상 무조건 선택해야 하므로 입력받은 배열을 그대로 dp배열로 넣어주었다.

3. 해당 칸을 선택하거나 선택하지 않는 경우가 있을수 있다. 선택한 경우와 선택하지 않은 경우중 큰 값을 가지고 가게 하였다.

 

 

 

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

1912번: 연속합