문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
예제 입력 1 복사
10
10 -4 3 1 5 6 -35 12 21 -1
예제 출력 1 복사
33
예제 입력 2 복사
10
2 1 -4 3 4 -4 6 5 -5 1
예제 출력 2 복사
14
예제 입력 3 복사
5
-1 -2 -3 -4 -5
예제 출력 3 복사
-1
[문제 풀이]
임의의 수열이 주어졌을 때 이 수열에서 연속하는 값들을 더했을 때의 가장 큰 값을 구하는 문제이다.
하나 이상의 값을 더해야 한다.
연속하는 값들을 더하는 경우는 여러가지가 존재할 것이다.
하나의 값만 선택할 수도 있을 것이고, 두 개 이상의 값을 선택하여 더할 수도 있다.
코드는 수열을 순회하면서 dp값을 채운다.
수열의 첫번째값을 기본으로 리스트에 저장하고
그 값과 다음값을 더한 경우가 첫 번째 값만 선택했을 때보다 더 크다면 그 값을 dp에 저장한다.
그러면 dp[1] = numbers[0]+numbers[1] 이 될 것이다.
이런 식으로 반복하다 보면 앞에서 누적해서 더해온 값보다 현재 수열의 값이 더 크다면
현재 값부터 다시 더하게 된다.
문제에서 제시한 예시를 살펴보면
10, -4, 3, 1, 5, 6, -35, 12, 21, -1
이라는 수열이 존재할 때
numbers = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]
dp = [10]
인 상태로 for문을 시작하게 된다.
i=1부터 시작한다
dp[0] = 10
i=1
numbers[1] = -4 > dp[0]+numbers[1] = 10 - 4 = 6
dp = [10, 6]
i=2
numbers[2] = 3 < dp[1]+numbers[2] = 6+3 = 9
dp = [10, 6, 9]
i=3
numbers[3] = 1 < dp[2]+numbers[3] = 9+1 = 10
dp = [10, 6, 9, 10]
i=4
numbers[4] = 5 < dp[3]+numbers[4] = 10 + 5 = 15
dp = [10, 6, 9, 10, 15]
i=5
numbers[5] = 6 < dp[4]+numbers[5] = 15 + 6 = 21
dp = [10, 6, 9, 10, 15, 21]
i=6
numbers[6] = -35 < dp[5]+numbers[6] = 21 + (-35) = -14
dp = [10, 6, 9, 10, 15, 21, -14]
i=7
numbers[6] = 12 > dp[6]+numbers[7] = (-14) + 12 = -2
dp = [10, 6, 9, 10, 15, 21, -14, 12]
i=8
numbers[6] = 21 < dp[7]+numbers[8] = 12 + 21 = 33
dp = [10, 6, 9, 10, 15, 21, -14, 12, 33]
i=9
numbers[6] = -1 < dp[8]+numbers[9] = 33 + (-1) = 32
dp = [10, 6, 9, 10, 15, 21, -14, 12, 33, 32]
max => 33
[소스 코드]
import sys
input = sys.stdin.readline
n = int(input())
numbers = list(map(int, input().split()))
dp = []
dp.append(numbers[0])
for i in range(1,len(numbers)):
dp.append(max(numbers[i], dp[i-1]+numbers[i]))
print(max(dp))
'알고리즘 > python' 카테고리의 다른 글
[python/파이썬] 백준 1890 점프 (0) | 2022.04.26 |
---|---|
[python / 파이썬] 백준 11053 가장 긴 증가하는 부분 수열 (0) | 2022.04.13 |
[python/파이썬] 백준 2407 조합 (0) | 2022.04.11 |
[python/파이썬] 백준 11727 2xn 타일링2 (0) | 2022.04.08 |
[python/파이썬] 백준 2579 계단 오르기 (0) | 2022.04.07 |