출처 | https://www.acmicpc.net/problem/1912
코드
n = int(input())
m = list( map(int, input().split(' ')))
for i in range(1, n):
m[i] = max(m[i], m[i] + m[i-1])
print(max(m))설계
-
첫 번째. i번째 데이터 이전까지 합을 계산해 봤을 때 최대값을 지속적으로 기록한다.
- 원칙1. 이전까지의 합이, 그냥 i번째 숫자보다 작은 경우 이전의 기록들은 무의미하다. 그러니 그냥 i번째 숫자를 최대값으로 설정한다.
코드 설명
-
반복문의 시작을 1에서 하는 이유
: 문제 풀이의 핵심은 "이전까지 모든 숫자의 합 중 최대값"을 그때그때 기록하는 것이다.
데이터의 시작점인 0번 인덱스는 이전까지의 합이 0 자신 자체이기 때문에 아무런 필요가 없다.
그래서 반복문의 시작은 1부터 한다.
- m[i] = max( m[ i ], m[ i ] + m[ i-1 ]) -> i번 째 데이터를 업데이트하는 이유
: i번째 인덱스는 핵심코드의 논리인 "이전까지 모든 숫자의 합 중 최대값"이기 때문에 수정을 해 주어야 한다.
예를 들어서 10번째 인덱스를 계산할 차례인데, 9번째 인덱스까지의 모든 경우의 수를 다시 계산하면 시공간 복잡도가 낭비되는 단점이 있다.
그래서 그냥 data의 9번째 값 자체를 이때까지 나온 모든 경우의 수 중에서 가장 최대값으로 업데이트를 하는 것이다.
이 부분은 아래의 시뮬레이션을 보면 이해가 빠르다
(3) 코드로 돌아가는 테스트 케이스 시뮬레이션
1) 기본 데이터 준비
n
m = [ 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 ]
첫 번째 Loop. i = 1
m[1] = max( -4, -4+ 10 = 6 ) -> m[1] = 6
m = [ 10, 6, 3, 1, 5, 6, -35, 12, 21, -1 ]
이때 6은 이전까지 연속된 합 중 최대값을 기록한 것이다. DP - Memorization
두 번째 Loop. i = 2
m[2] = max( 3, 3+6= 9) -> m[2] = 9
m = [ 10, 6, 9, 1, 5, 6, -35, 12, 21, -1 ]
9 또한 이전가지 연속된 합 중 최대값을 기록한 것이다.DP - Memorization
이렇게 루프가 다 돌았을 때 나오는 데이터의 경우의 수는 아래와 같다.
m = [10, 6, 9, 10, 15, 21, -14, 12, 33, 32]
그래서 m 중에서 가장 큰 수는 33이기에 정답이 되는 것이다.
