문제:
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12 + 21 인 33이 된다.
입력:
첫째 줄에 정수 n(1<=n<=100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력:
첫째 줄에 답을 출력한다.
풀이 방법:
DP를 활용해서 푸는 문제이다. 반복문은 여러개 써야 할 것 같지만 배열 한 번을 탐색하는 반복문 하나로도 풀 수 있다. 정답을 maxsum이라 하고 초기값을 -1000으로 잡아준다. 왜냐하면 모든 수는 -1,000보다는 크기 때문이다. 배열중 임의의 값과 그 전부터 누적해온 값 중 더 큰 값을 선택하고 이를 maxsum과 비교해서 maxsum보다 커지는 값들이 있다면 그 값을 maxsum으로 갱신해준다.
예시 케이스로 설명하면 다음과 같이 된다.
처음에는 max(10,0+10)이므로 temp가 10이 되고 maxsum은 당연히 10으로 최신화된다.
그 다음에는 max(-4,10-4)이므로 temp가 6이 되지만 maxsum은 유지된다.
max(3,6+3)이므로 temp가 9가 되지만 maxsum은 유지된다.
max(1,9+1)이므로 temp가 10이 되지만 maxsum은 유지된다.
max(6,10+6)이므로 temp가 16이 되고 maxsum이 16이 된다.
max(-35,16-35)이므로 temp가 -19가 되고 maxsum은 유지된다.
max(12,-19+12)이므로 temp가 12가 되고 maxsum은 유지된다.
max(21,12+21)이므로 temp가 33이 되고 maxsum은 갱신된다.
max(-1,33-1)이므로 temp가 32가 되고 maxsum은 유지된다.
따라서 12+21인 33이 정답이 된다.
1 2 3 4 5 6 7 8 9 | n=int(input()) arr=list(map(int,input().split())) temp=0 maxsum=-1000 for num in arr: temp=max(num,temp+num) if temp>maxsum: maxsum=temp print(maxsum) | cs |
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1149. RGB거리 (0) | 2019.04.21 |
|---|---|
| [BOJ]2163. 초콜릿 자르기 (0) | 2019.04.20 |
| [BOJ]2504. 괄호의 값 (0) | 2019.04.18 |
| [BOJ]9012.괄호 (0) | 2019.04.17 |
| [BOJ]1874. 스택 수열 (0) | 2019.04.16 |