[백준] C++ 1912번 : 연속합

풀이과정

---

점화식 : d[1] = v[1], (n>1) d[n] = max( d[n-1] + v[n] , v[n] )

 

n개의 정수가 주어질 때, d[1] ~ d[n] 의 값 중 가장 큰 값이 제일 큰 연속합.

코드

---

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	int d[100001] = { -1000, };
	int iValue[100001] = { 0, };

	int iInput = 0;

	cin >> iInput;

	for (int i = 1; i <= iInput; ++i)
	{
		cin >> iValue[i];

		if (i == 1) d[1] = iValue[1];
		else d[i] = max(d[i - 1] + iValue[i], iValue[i]);
	}
	for (int i = 1; i <= iInput; ++i)
	{
		if (d[0] < d[i]) d[0] = d[i];
	}

	cout << d[0] << endl;
	return 0;
}