[백준] 1912번(연속합)

백준 1912번

최종 제출 코드

n = int(input())
array = list(map(int, input().split()))

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

print(max(array))

◼ 처음부터 i번째 원소까지 중, i번째 원소를 무조건 포함하여 합이 최대가 되는 연속된 집합의 합을 값을 구한다.

◼ max(array[i-1]+array[i], array[i])

• array[i-1]+array[i] > array[i]이면 앞의 원소들을 더하는 것이 이득이 된다.
• array[i-1]+array[i] < array[i]이면 앞의 원소들을 더하는 것이 손해가 되어, i번째 원소만을 집합의 원소로 갖는 것이 낫다.