[백준/Python] 1912 연속 합

[백준/Python] 1912 연속 합

정답 코드 및 설명

전체 코드

import sys
def max_subarray_sum(A):
    max_sum = current_sum = A[0]
    
    for i in range(1, len(A)):
        current_sum = max(A[i], current_sum + A[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

input = sys.stdin.readline

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

print(max_subarray_sum(input_list))

문제 설명

위 문제는 연속합 중 가장 큰 값을 구하는 것이다. 연속 합이라고 하면 처음 항 부터 끝까지 모두 더 한 값도 포함되고, 하나의 원소 또한 포함될 수 있다. 또한 1번째 ~ 3번째 까지만 더한 값, j 번째 부터 k 까지의 값을 더한 값 등 모두 될 수 있다.

코드 설명

입력 값 n 과 list 를 입력받아 먼저 저장해준다.

input = sys.stdin.readline

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

그 후 함수를 호출하는 데 이 함수는 다음과 같은 형태를 가진다.

def max_subarray_sum(A):
    max_sum = current_sum = A[0]
    
    for i in range(1, len(A)):
        current_sum = max(A[i], current_sum + A[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

함수의 인자, A는 입력받은 배열이다.
max_sum = current_sum = A[0]
리스트 A 의 항목이 1개 이상이라고 간주하고, max_sum 지금까지 계산한 항목 중 가장 max 한 값을 저장할 것이다. current_sum 현재 계산한 sum 값이다. 초기화 해주는 것이다.

for i in range(1,len(A)) :
for 반복문으로 모든 항목을 거치면서 계산해주고 max 를 이용해 current 값을 구하고, 이를 비교해 큰 값을 저장해준다.

모든 항목에 대한 반복이 완료되었다면, max_sum 값을 리턴해준다.