문제

BOJ 1912: 연속합 https://www.acmicpc.net/problem/1912

풀이

조건

• n개의 정수로 이루어진 임의의 수열이 주어진다.
• 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.
• 수는 한 개 이상 선택해야 한다.

풀이 순서

• 시간복잡도를 고려했을 때 누적합 방식으로 해결해야한다.
• 누적합을 구해가면서 누적합 중 최소값을 구한다.
• 현재 누적합이 최소값이 아닌 상황
  • 지금까지의 최대값, 현재 누적값과 최소값의 차, 현재 누적값, 원본 배열의 현재 값 중 최대값을 구한다.
• 다음 누적합을 구하기 전에 지금까지의 최대값, 현재 누적값, 원본 배열의 현재 값 중 최대값을 구한다.
• https://www.acmicpc.net/board/view/44227 에서 예외 케이스를 얻어 해결했다....

코드

Python

import sys

n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rstrip().split()))

sum_arr = [0] * n  # 누적합 구할 배열
answer = arr[0]  # 배열 첫번째 값으로 초기화
sum_arr[0] = arr[0]  # 누적합 첫 번째 값은 배열 첫번째 값으로 초기화
min_value = arr[0]  # 누적합 중 최소값은 배열 첫번째 값으로 초기화

# 누적합을 구하면서 동시에 답을 찾음
for i in range(1, n):
    # 누적합 구하기
    sum_arr[i] = sum_arr[i - 1] + arr[i]
    # 누적합 중 최소값 찾기
    if min_value > sum_arr[i]:
        min_value = sum_arr[i]
    # 최소값이 아닌 상황에선 지금까지의 최대값, 현재 누적값과 최소값의 차, 현재 누적값, 원본 배열의 현재 값 중 최대값을 구함
    else:
        answer = max(answer, sum_arr[i] - min_value, sum_arr[i], arr[i])
        
    # 지금까지의 최대값, 현재 누적값, 원본 배열의 현재 값 중 최대값을 구함
    answer = max(answer, sum_arr[i], arr[i])

print(answer)

정리

• 예외 케이스 생각해내는 연습을 해야겠다.