[백준] 1912번 연속합

문제: 1912번: 연속합

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
//#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++)
		cin >> nums[i];

	int answer = nums[0];
	for (int i = 1; i < n; i++) {
		// 현재값이랑, 이전의 연속합 + 현재값 중 더 큰 값으로 갱신
		nums[i] = max(nums[i - 1] + nums[i], nums[i]);

		if (nums[i] > answer)
			answer = nums[i];
	}
	cout << answer << "\n";

	return 0;
}

 

현재값이랑 이전의 연속합 + 현재값 중 더 큰 값으로 갱신해주면 쉽게 해결할 수 있는 문제이다.

 

 

 

참고자료:

Kadane's algorithm 이란? (설명)

Kadane's algorithm 이란? (설명)