문제

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. 나의 해결방법 및 소스코드

1. 수를 처음부터 계속 result에 더해나가면서 합을 '최대 힙' 기반의 '우선순위 큐'에 넣어준다.
2. 계속 더해나가다가 합이 음수가 되면 그 결과를 우선순위 큐에 넣은 후, result값을 0으로 초기화시킨다.
   그런 후에 다시 수를 더해나가며 result값을 업데이트 해주고 우선순위 큐에 넣어준다.
3. 우리가 구하려는 답은 우선순위 큐의 맨 위에 있다.
4. 2번에서 result값을 0으로 초기화시키고 다시 그 다음부터 합을 더해나가는 이유는, 우리는 연속된 부분합의 최대를 원하는 것인데, 이미 어느부분까지의 부분합이 음수로 전환되었다면, 그 뒤에 나오는 수를 거기에다가 더하는 것보단 result를 그 뒤에 나오는 수부터 다시 더해나가는 편이 당연히 더 크기 때문이다.

#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; int main() { int N, x; int result = 0; vector<int> numbers; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d", &x); numbers.push_back(x); } //모든 정보 입력 완료 priority_queue<int> maxsum; for (int i = 0; i < N; i++) { // printf("현재 검사하는 수: %d\n", numbers[i]); result += numbers[i]; if (result < 0) { // printf("%d를 큐에 넣습니다\n", result); maxsum.push(result); result = 0; } else { // printf("%d를 큐에 넣습니다\n", result); maxsum.push(result); } } printf("%d\n", maxsum.top()); }

2. Dynamic Programming을 이용한 풀이

이 풀이도 나의 풀이와 맥락은 통한다. 전체 합이 음수가 되면 연속합을 다시 시작하는 것이 핵심 아이디어이다.

• n번째 수에서의 연속합의 최대값을 dp[n]이라고 하자.
• 그러면 dp[n]은 다음과 같이 정의될 수 있다.

  dp[n] = max(dp[n-1] + arr[n], arr[n])

• 우리가 구하는 정답을 나타내는 ans 변수는 dp배열이 업데이트 될 때마다 자기자신과 비교하여 더 큰 값이 나타나면 그것으로 업데이트해준다.

#include <iostream> #include <algorithm> using namespace std; int main(){ int N; int ans; int arr[100005]; int dp[100005]; scanf("%d", &N); for(int i=0; i<N; i++) scanf("%d", &arr[i]); dp[0] = arr[0]; ans = arr[0]; for(int idx = 1; idx < N; idx++){ dp[idx] = max(dp[idx-1] + arr[idx], arr[idx]); if(ans < dp[idx]) ans = dp[idx]; } printf("%d\n", ans); }