문제링크
https://www.acmicpc.net/problem/1912
문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.
입력
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
출력
첫째 줄에 답을 출력한다.
조건
- 시간 제한 : 1s
- 메모리 제한 : 128MB
해설
K번째 숫자를 고려한다고 했을 때, K-1번째 숫자까지의 최댓값에 K를 더하면 더 커질지, 아니면 앞을 버리고 K번째 숫자부터 다시 수를 더해나갈지를 결정하고, 앞의 최댓값과 다시 수를 더해 만든 최댓값을 비교해 찐 최댓값을 출력하면 원하는 결과를 얻을 수 있다.
풀이
먼저, 숫자는 arr[i]에 담기고, X번째 수 ~ i번째 수까지의 연속합은 arrSum[i]에 저장된다. maxSum은 현재까지 나온 연속합의 최댓값이다.
위 해설의 말을 코드와 함께 다시 살펴보자
K번째 숫자를 고려한다고 했을 때, K-1번째 숫자까지의 최댓값에 K를 더할지, 아니면 K부터 다시 숫자를 더해나갈지 결정해야 한다. [ 6 -35 123 ] 이 주어졌다고 해보자. 123을 고려할 때는 -29에 123을 더할지, 123부터 다시 수를 세어나갈지 골라야 한다. 이 경우 123을 고르는 것이 더 최댓값을 만들 수 있다. arrSum[2]에는 123이 저장된다.
arrSum[i] = max(arrSum[i-1]+arr[i], (long)arr[i]);
지금까지 만들었던 부분합의 최댓값과 이번에 만든 arrSum의 값을 비교하여 더 큰 값을 부분합의 최댓값으로 저장한다. [ 21 -35 12 21 4 ] 이 주어졌다고 해보자. 12에서의 arrSum은 12이지만(앞에서 연결하는 것보다 12부터 새로 더하는게 더 크니깐 arrSum[2] = 12), 부분합의 최댓값은 21이다. 21에서는 arrSum이 33이 되어 부분합의 최댓값도 33으로 대입해야한다.
maxSum = max(arrSum[i], maxSum);
모든 원소를 처리한 뒤 maxSum에 담긴 수를 출력하면 원하는 결과를 얻을 수 있다.
코멘트
너무 어렵게 생각하고 있었던 것 같아. 생각보다 쉬운 일이였는데... ㅜㅜ
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> arr(N);
vector<long> arrSum(N);
long maxSum = 0;
// set initial value
cin >> arr[0];
arrSum[0] = arr[0];
maxSum = arr[0];
for(int i = 1; i < N; i++) {
cin >> arr[i];
// arrSum[i-1]+arr[i] → 수열이 증가하고 있음
// arr[i] → 앞에 합치는 것보다 arr[i]를 고르는 것이 더 큼
arrSum[i] = max(arrSum[i-1]+arr[i], (long)arr[i]);
// 기존의 sum이 더 큰지, 새로 만든 arrSum[i]가 더 큰지 비교
maxSum = max(arrSum[i], maxSum);
}
cout << maxSum;
return 0;
}
Uploaded by Notion2Tistory v1.1.0