[BAEKJOON]1912 연속합

첫번 째 코드

#include <iostream> #include <vector> #include <fstream> #include <algorithm> using namespace std; vector<int> number; vector<int> cache; int main() { ifstream fcin; fcin.open("1912_input.txt"); int number_count; fcin >> number_count; number = vector<int>(number_count); cache = vector<int>(number_count, -1); for (int j = 0; j < number_count; j++) fcin >> number[j]; int max_sum = -1; cache[0] = number[0]; for (int j = 0; j < number_count - 1; j++) { cache[j] + number[j + 1] < 0 ? cache[j + 1] = 0 : cache[j + 1] = cache[j] + number[j + 1]; max_sum = max(max_sum, cache[j + 1]); } cout << max_sum << endl; system("pause"); }

이 문제를 이전에 본 적이 있다.

알고스팟에서 나온 문제였는데 이것또한 연속합을 구하는 문제였다.

따라서 그 문제를 기억해서 풀었다.

하지만 중간에 오답 왜일까?

이유는 위의 코드에서는 음수가 나오면 저절로 그 음수는 연속합이 큰 것이라고 가정하지 않는다.

따라서 0으로 변경해준다.

하지만 -1 -2 -3이 나올때는 어떨까 최대는 -1이다

두번째 코드 (정답)

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int arr_count; cin >> arr_count; vector<int> number = vector<int>(100001); vector<int> cache = vector<int>(100001); for (int i = 1; i <= arr_count; i++) cin >> number[i]; cache[1] = number[1]; int Max = cache[1]; for (int i = 2; i <= arr_count; i++) { cache[i] = max(cache[i - 1] + number[i], number[i]); Max = max(Max, cache[i]); } cout << Max << endl; }