💡 문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
💭 접근
dp 리스트에 각 a 리스트의 마지막 원소가 더해졌을 때의 총 합을 저장해준다. 이때, 이전까지의 합이 a[i]보다 작은 경우 이전의 합들은 의미가 없기에 a[i]를 최대값으로 저장한다. 따라서 점화식은 dp[i] = max(a[i], dp[i - 1] + a[i])가 된다.
ex) 예제
i = 1, a[1] = -4
dp = [10, 6, 0, 0, 0, 0, 0, 0, 0 ,0]
i = 2, a[2] = 3
dp = [10, 6, 9, 0, 0, 0, 0, 0, 0, 0]
...
i = 6, a[5] = -35
dp = [10, 6, 9, 10, 15, 21, -14, 0, 0, 0]
i = 6, a[6] = 12
dp = [10, 6, 9, 10, 15, 21, -14, 12, 0, 0]
i = 7, a[6] = 21
dp = [10, 6, 9, 10, 15, 21, -14, 12, 33, 0]
...
📒 코드
n = int(input())
a = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dp[0] = a[0]
for i in range(1, n):
dp[i] = max(a[i], dp[i - 1] + a[i])
print(max(dp))💭 후기
언제 합을 새로 시작해야 하는지 조건을 찾으면 쉽게 풀리는 문제.
🔗 문제 출처
https://www.acmicpc.net/problem/1912
