(파이썬) Baekjoon Online Judge 백준 1912 연속합
문제
풀이
예제 입력을 먼저 따져보면,
| 번호 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| N | 10 | -4 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
| 최대합 | 10 |
A 에는 바로 이전 인덱스 까지의 최대합(10)과 -4를 더한값과 -4를 단독 선택했을때 큰 경우를 입력한다 → 6이 입력될 것이다.
| 번호 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| N | 10 | -4 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
| 최대합 | 10 | 6 | 9 |
6+3 과 3을 비교하면 9가 더 크기 떄문에 다음칸은 9
같은 방식으로 진행해보면…
| 번호 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| N | 10 | -4 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
| 최대합 | 10 | 6 | 9 | 10 | 15 | 21 | -7 |
이제 여기서 -7+12와 12를 비교하였을 때, 12의 단독 선택이 더 크다.
| 번호 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| N | 10 | -4 | 3 | 1 | 5 | 6 | -35 | 12 | 21 | -1 |
| 최대합 | 10 | 6 | 9 | 10 | 15 | 21 | -7 | 12 | 33 | 32 |
결국 이렇게 완성되는데, 최대합중 가장 큰 33이 최대값이 되고, 이는 12 와 21을 더한 결과가 된다.
최대합을 sum, 입력된 숫자를 num이라 하면
sum[i] = max(sum[i-1] + num[i], num[i])
코드
파이썬 (python)
|
1 2 3 4 5 6 7 |
n=int(input()) num=[0]+list(map(int,input().split())) sum=[num[0]] # num[0]으로 시작 for i in range(1,n+1): sum.append(max(sum[i-1]+num[i], num[i])) print(max(sum[1:])) |