문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력
10
10 -4 3 1 5 6 -35 12 21 -1
예제 출력
33
풀이
풀이법이 생각이 안나서 다소 시간을 사용하였다. 브루트포스에서 dp 방법으로 도달하기까지의 풀이를 적어보았다.
가장 쉬운 방법으로 브루트포스 방법을 생각할 수 있다. 브루트포스 방법은 기존의 결과값을 재사용하지 않고 일일이 계산한다.
브루트 포스 방법
# 1. 앞에서부터 오른쪽으로 계산
n = int(input())
arr = list(map(int, input().split()))
print(arr)
mx = arr[0]
for i in range(n):
sum = arr[i]
for j in range(i+1, n):
sum += arr[j]
mx = max(sum, mx)
print(mx)
# 2. 앞에서부터 왼쪽으로 계산
mx = arr[0]
for i in range(n):
sum = 0
for j in range(i, -1, -1):
sum += arr[j]
mx = max(mx, sum)
print(mx)아직 dp에 도달하지는 않았지만 각 인덱스의 결과값을 저장해보자. 여전히 브루트포스 방법이다. 재사용을 위해 왼쪽으로 가며 계산하는 모습을 볼 수 있다. 그러나 재사용은 하지 않는다. dp로 가는 과정이랄까..
# dp 로 가기 위한 전단계, 결과 저장(결괏값 재사용 위해,but 여기선 재사용 X)
max_arr = [0] * n
for i in range(n):
sum = 0
for j in range(i, -1, -1):
sum += arr[j]
max_arr[i] = max(max_arr[i], sum)
print(max(max_arr)) dp 방법
dp 방법에서는 기존의 값을 재사용한다. 재사용을 위한 배열(1: dp, 2: arr)엔 해당 숫자가 해당 숫자로부터 왼쪽에 있는 값들과 더해져서 가질 수 있는 가장 큰 값이 들어있다.
왼쪽에서부터 시작하게 되면
10 -4 3 1 5 6 -35 12 12 -1 이 있다고 가정할 때
10 은 그 자체로 해당 숫자가 해당 숫자로부터 왼쪽에 있는 값들과 더해져서 가질 수 있는 가장 큰 값 이다. -4 는 10 + -4, -4 중 더 큰 값을 결과로 가진다. 3 은 (-4가 결과로 가진 값 + 3)과 3 을 비교해 더 큰 값을 결과로 가진다. 자기 자신을 결과로 할지 그 전까지의 숫자들을 더했을때 가진 최대의 값 + 자기 자신을 결과로 할지 결정하는 과정이다.
만약 오른쪽 방향으로 계산하게되면, 큰 범위의 결과를 작은 범위가 재사용할 수 없기 때문에 왼쪽으로 계산하며 결과를 저장해야 한다.
기존의 배열을 변형시키지 않고 따로 dp 배열을 생성하는 경우와, 그렇지 않은 경우로 2가지 방법이 있다.
# 1. 기존 배열 재사용 X
dp = [0] * n
dp[0] = arr[0]
for i in range(1, n):
dp[i] = max(dp[i-1] + arr[i], arr[i])
print(max(dp))
# 2. 기존 배열 재사용 O
for i in range(1,n):
arr[i] = max(arr[i-1]+arr[i], arr[i])
print(max(arr)) 