백준 온라인 저지의 1912번 연속합 문제입니다.
[링크] https://www.acmicpc.net/problem/1912
문제 조건과 설명
- n개의 정수로 이루어진 임의의 수열이 주어집니다.
- 이 중에서 ‘연속된 몇 개의 수’를 선택해서 구할수 있는 합 중 가장 큰 합을 구합니다.
- 예를 들어 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어진다면, 정답은 12+21=33입니다.
Input
첫째 줄에는 정수 n(1<=n<=100,000)이 주어집니다.
둘째 줄에는 n개의 정수로 이루어진 수열이 주어집니다.
수열에 있는 수는 -1000 보다 크거나 같고, 1000보다 작거나 같은 정수입니다.
Output
첫째 줄에 연속된 몇 개의 수를 선택하여 구할 수 있는 가장 큰 합을 출력합니다.
생각한 아이디어
연속된 숫자를 더한 합을 구하는 것이기 때문에, 직전까지 더해진 값과 현재 값을 더하는 계산이 중요하다고 생각했습니다. -> 다이나믹 프로그래밍
연속된 숫자를 더하는데, 계속 양수가 더해진다면 가장 적합한 예시일 것입니다.
그러나 연속된 숫자를 더해가는데 음수가 된다면 답과 거리가 멀 것입니다.
즉 음수가 되는 그 시점을 경계로 삼는다고 생각하면 편합니다.
다만, 모든 요소가 음수일 경우가 있을 수 있는데, 이 때에는 그들 중 가장 값이 큰 것을 골라주면 됩니다.
[예] 2, 1, -4, 3, 4, -4, 6, 5, -5, 1 수열이 있을 때
- 우선 dp[0] = arr[0] 으로 초기화, max 값도 dp[0] 값으로 설정
- arr[1] 과 dp[0]+arr[1] 중 더 큰 값을 dp[1]에 대입 -> dp[1] = 3
- arr[2]와 dp[1]+arr[2] 중 더 큰 값을 dp[2]에 대입 -> dp[2] = -1
- arr[3]과 dp[2]+arr[3] 중 더 큰 값을 dp[3]에 대입 -> dp[3] = 3
- arr[4]와 dp[3]+arr[4] 중 더 큰 값을 dp[4]에 대입 -> dp[4] = 7
- …
- 자기 자신의 값과, 지금까지 더해진 값에 자신을 더한 값 중 더 큰 값을 dp 배열에 넣습니다.
- 직전까지의 합에 자기 자신의 값을 더했는데도 자기 자신보다 값이 작다면, 직전까지의 합은 음수였다는 이야기가 됩니다. 따라서, 연속된 수의 합을 그 때 이후부터는 자기 자신부터 다시 시작하는 것입니다.
- 매 반복문마다 수시로 최댓값은 체크합니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
int arr[100001];
int dp[100001];
int main() {
int n, sum = 0, input = 0;
int maxV = -10000;
int ans;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &input);
arr[i] = input;
}
ans = arr[0];
dp[0] = arr[0];
for(int i=1;i<n;i++){
dp[i]=max(arr[i],dp[i-1]+arr[i]);
ans=max(ans,dp[i]);
}
printf("%d", ans);
}