백준 1912 연속합 c++ [hard]// dp, 연속합중 최대값 구하는 방법

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

1912번: 연속합

1. 나의틀린풀이

나의틀린풀이 : d[i]=max(d[i-1], d[i-1]+a[2], a[2]_

d[i]=max(포함x, 포함o, 새로운값)

 

2. 정답코드

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);
}