[Baekjoon/🥈SilverⅡ] 1912: 연속합

Intro

접근 방법🙋‍♀️

• 여기서 핵심은 👏연속👏이다.
  • 즉, 우리가 고려해야 할 것은 현재 수와 이전 수이다.
  • 단, 여기서의 이전 수는 👏이전 수를 포함해 구한 연속된 수들의 합👏이다.
    • 여기서 dp 적용!!

그렇다면 각 단계에서 구해진 수들의 합을 살펴보자.

• 문제의 예제 입력 1의 경우를 살펴보자.

  

  • 🙋‍♀️ dp[i] = ?
    • i-1번째 dp값이 음이 아닐 경우, dp[i-1] + 현재 값
    • i-1번째 dp값이 음일 경우, 현재값

Algoritm👩‍💻

• 위 방식을 적용해 알고리즘을 작성해보자.

# 21.01.05
# 연속합
import sys

n = int(input())
nums = list(map(int, sys.stdin.readline().rstrip().split()))
dp = [0 for i in range(n)]
dp[0] = nums[0]

for i in range(1, n):
  if dp[i-1] < 0:
    dp[i] = nums[i]
  else:
    dp[i] = dp[i-1] + nums[i]

print(max(dp))

그럼 이만!!

끝!! ~(˘▾˘~)