1912 연속합

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

"""
임의의 수열이 주어지고,
<<연속된>>몇개의 수를 선택해 구할 수 있는 것중 가장 큰 합을 구하자.
정렬은 안하는 듯.
"""

import sys
read = sys.stdin.readline
N = int(read())
array = list(map(int,read().split()))

"""
자기자신 vs 자기 전의 것과 더한 것을 비교하면 알아서 될듯.
"""

dp_table = [0 for _ in range(N)]

dp_table[0] = array[0]

for i in range(1,N):
    now = array[i]
    dp_table[i] = max(now,dp_table[i-1]+now)

print(max(dp_table))

3. 풀이 및 생각

문제 풀이

이 문제는 일반적인 dp를 생각해서 풀면 된다. max(now,dp[i-1]+now)를 하는 순간을 보면, dp[i-1]+now의 뜻은 이전에 있던 값하고 연속해서 수열을 선택할 것인지를 뜻하고, now는 이전의 값들이랑 이어지는 것보다 지금 값부터 시작하는게 더 크니까 선택한다는 느낌을 가지면 된다.

나의 생각

-