백준 1912번 : 연속합

<문제>

링크 : https://www.acmicpc.net/problem/1912

1912번: 연속합

---

<코드>

import sys
input = sys.stdin.readline

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

arr_sum = [0] * n
arr_sum[0] = arr[0]
for i in range(1, n):
    if arr_sum[i-1] > 0 :
        arr_sum[i] = arr_sum[i-1]+arr[i]
    else:
        arr_sum[i] = arr[i]
        
print(max(arr_sum))

---

<풀이>

수열의 원소를 양수들의 조합과 음수들의 조합으로 나누어 생각한다. 

양수인 연속된 수열의 합이 가장 클 수 있고 음수를 일부 포함하고 연속된 수열의 합이 가장 클 수 있으므로 양수만을 고려하면 정확한 해를 찾지 못한다.

예를 들어, [양수들] [음수들] [양수들] 로 수열이 구성된 경우 가운데 있는 음수들의 합의 크기가 앞선 양수들의 합의 크기보다 작은 경우 전체 수열의 합이 연속된 수열에서 가장 큰 합을 구할 수 있고 그 크기가 음수쪽이 더 큰 경우 앞선 양수까지 연속된 수열로 포함하지 않아야 한다. -3, 4, 1 인 경우 앞의 음수는 포함하지 않고 뒤의 양수만 구성된 수열에서 가장 큰 합을 구할 수 있고 4, -3, -2, 6에서 가운데 음수를 포함하지 않는 것이 가장 큰 합을 구할 수 있게 된다.

즉, 양->음->양 으로 넘어가는 경우 음수 포함 여부를 결정하는 것이 중요한데 정리를 하자면, 경우의 수로 앞선 수열에서 합이 +, -인 경우와 특정 위치의 원소가 +, -인경우로 네가지 경우가 있고 각 경우에 따라 연속된 수열의 합이 최대가 되도록 값을 새로운 배열에 저장하도록 한다.

 

※ 4가지 경우의 수

1. 앞선 수열의 합이 +, 특정 원소가 + : 두 값 합하기
2. 앞선 수열의 합이 +, 특정 원소가 - : 두 값 합하기
3. 앞선 수열의 합이 -, 특정 원소가 + : 특정 양의 원소 값으로 대체
4. 앞선 수열의 합이 -, 특정 원소가 - : 특정 음의 원소 값 대체

---

참고 : https://github.com/Junuux/Algorithm/tree/main/Silver/1912

GitHub - Junuux/Algorithm