1912연속합파이썬

0. 최종코드

python
n = int(input())
input_list = list(map(int, input().split()))
total_max = input_list[0]
current_max = input_list[0]
for i in range(1, len(input_list)):
    current_max = max(input_list[i], input_list[i] + current_max)
    total_max = max(total_max, current_max)
print(total_max)

1. 이론 설명

정의

연속 부분 수열이란, 주어진 수열에서 인접한 원소들로 이루어진 부분 수열을 의미함. 예를 들어, 수열 [1, -2, 3, 4]이 주어졌을 때, 연속 부분 수열은 [1], [1, -2], [3, 4] 등 여러 개가 있을 수 있음.

이 문제는 주어진 수열에서 연속된 부분 수열 중 가장 큰 합을 찾는 문제임. 이 문제를 해결하기 위해선 동적 계획법(DP, Dynamic Programming)을 사용함.

주요 개념

주어진 문제는 동적 계획법을 이용해 풀 수 있음. 이때 중요한 개념은 현재 위치까지의 연속 부분 수열의 최댓값을 저장해 나가는 방식임.

1. current_max

current_max는 현재 위치에서 끝나는 연속 부분 수열의 최댓값을 의미함. 즉, 수열의 현재 인덱스 i에서, input_list[i]를 포함하는 연속 부분 수열의 최대 합을 나타냄. 이것은 두 가지 값 중 큰 값을 선택해서 구함:

• 새로운 부분 수열을 시작할지 (input_list[i])
• 이전까지의 연속 부분 수열에 이어서 더할지 (input_list[i] + current_max)

2. total_max

total_max는 전체 수열 중에서 가장 큰 연속 부분 수열의 합을 저장함. 매 반복마다, 현재까지 계산된 current_max와 기존 total_max를 비교하여 더 큰 값을 저장함.

점화식

• current_max = max(input_list[i], input_list[i] + current_max)
• total_max = max(total_max, current_max)

과정

1. 처음에는 수열의 첫 번째 값을 current_max와 total_max로 설정함.
2. 그 이후에는 두 번째 값부터 수열 끝까지 위의 점화식을 적용하여 각 인덱스에서의 최댓값을 갱신해 나감.