👩🏻‍💻 문제링크

https://www.acmicpc.net/problem/1912

1912번: 연속합

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

✍️ 아이디어

1. 문제 이해

연속해서 더할수 있는 수중에 가장 큰 수를 찾자

2. 점화식 D[ i ] = i번째 수로 끝나는 가장 큰 연속합

3. i번째 수열과 i-1번째 점화값과 i번째 수열을 더한 것중에 큰것을 저장한다

A[i] < A[i]+result[i-1] //A[i]는 수열 result는 값 저장 공간

✍️소스코드

이 아이디어는 강의 안봤으면 절대 안떠올랐을거 같다..(남의 코드는 내코드랑 비슷해서 패스~)

#include <iostream>
#include <algorithm>
using namespace std;
int result[100001];

int main()
{
	int A[100001];
	int n; cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>A[i];
	}
	result[1]=A[1];
	for(int i=2; i<=n; i++)
	{
		if(A[i]<A[i]+result[i-1])
		{
			result[i]=A[i]+result[i-1];
		}
		else{
			result[i]=A[i];
		}
	}
	cout<<*max_element(result+1, result+n+1)<<'\n';
}

체감난이도	걸린시간	참고	사용 문법
최상	1hour	강의 참고	Dp