백준 1912 연속합 c++ // dp, 규칙발견, ox를 그때그때 선택해버리기

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

1912번: 연속합

1 . ox를 그때그때 선택해버리기

1.완탐 : i번째수를 선택함, 안함으로 2^n 탐색해야함

2. 선택한경우 vs 선택안한경우에서 최적인 경우를 그때그떄 선택한다.

 

3. 이전값 + 현재값() vs 현재값(나부터 연속합 새로시작)  중에 큰값을 선택하면 된다.

 

2.전체코드

#include <bits/stdc++.h>
using namespace std;

long long d[100004], a[100004],n;
//d[i]: i자리까지 연속합중 최대값 

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

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		d[i] = a[i];
	}

	d[1] = a[1];

	for (int i = 2; i <= n; ++i) {
		d[i] = max(a[i], d[i - 1] + a[i]);
		//d[i]=max(현재값[새로시작], 이전값+현재값)
	}

	//각각 i자리까지의 최대값이 저장됨
	//d[n]이 최대값 보장이아님 -> 최대값찾으면됨.
	cout << *max_element(d + 1, d + n + 1);
}