문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
#처음 짜서 제출한 코드 (이것도 정답은 뜸)
N = int(input())
S = list(map(int,input().split()))
dp = [0] * N
def maxPrefixSum():
global dp
if N==1:
print(S[0])
return
else:
dp[0] = S[0]
dp[1] = max(S[1],S[0]+S[1])
for i in range(2,N):
dp[i] = max(dp[i-1]+S[i],S[i])
print(max(dp))
maxPrefixSum()
#불필요한 부분 제거한 코드
#생각해보니 dp[0]만 사전에 넣어두고 시작하면 됨
N = int(input())
S = list(map(int,input().split()))
dp = [0] * N
def maxPrefixSum():
global dp
dp[0] = S[0]
for i in range(1,N):
dp[i] = max(dp[i-1]+S[i],S[i])
print(max(dp))
maxPrefixSum()DP 공부한지 이틀차, 여태 한 문제도 내 힘으로 못 풀다가 처음으로 스스로 푼 문제이다.
직관적으로 이 문제는 재귀를 안 쓰고 반복문을 쓸 수 있겠다는 생각이 들었다.
그 다음으로 어떻게 sub-problem으로 나눌 수 있을까 고민했고, DP라는 배열이 있다면 이 배열은 무엇을 나타내는 것일까 역으로 생각해봤다.
DP의 각 원소는 S 배열에서 해당 인덱스 위치의 값이 그 이전 인덱스 값까지 가질 수 있는 연속 최대합이다.
처음에는 DP 배열 하나만 있으면 되나 생각했는데, 연속합이 아닌 원래 수를 더해야하므로 원본 입력 숫자들을 갖고 있는 배열 하나가 더 필요하다 (S)
max로 2개 이상의 기준을 비교해서 하나를 취해야 한다는 아이디어는 떠올랐는데, 이 기준 중 하나가 자기 자신이다.
문제에서 힌트를 얻은 부분은 ‘단, 수는 한 개 이상 선택해야 한다.’이다.
꼭 연속된 수와 더하지 않고 자신의 값을 그대로 가지고 있어도 되므로 비교 대상은 max로 큰 값을 취한다.
점화식은 dp[n] =max(dp[n-1]+S[n],S[n])이다.
반복문을 돌면서 각 Index는 더하지 않고 그대로 있던가, 아니면 그 전 값과 더하든가 선택한다.
연속합 수열의 갯수가 아닌 연속 최대합을 출력하는 것이므로 반복문을 다 돌고 DP 배열에서 Max값을 출력해주면 된다.
