[Day 1] 연속합

DP란 Dynamic Programming 을 축약한 단어로, 동적 프로그래밍이라 부른다.

이러한 DP를 푸는 방법은, 아직까지 경험에 의하면 

1. 재귀적 호출

2. 점화식

이 두가지의 경우가 대부분인 것 같다.

재귀적 호출은 반복문을 통해서도 해결할 수 있는데, 재귀적 호출의 경우 끝나야 하는 조건이 명확해야 재귀식안에서 탈출 가능하기 때문에

이와 같은 조건이 명확하게 떠오르지않는다면 반복문을 통해서 일부 확인하는 것도 좋은 방법이다.

위의 문제는 백준 1912 연속합 문제이다.

Num 배열은 입력받는 배열의 값을, DP배열은 현재위치까지의 최대합을 나타낸다.

이전의 합과 현재 자신의 위치 입력값을 비교하여 Max 값을 현재의 DP 배열안에 저장하도록 하고,

최종적으로 12, 21 즉 33이 최종 답이 된다.

<소스코드>

#include <cstdio>
#include <algorithm>
using namespace std;
int n, num[100001], dp[100001],maxx;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", num + i);
	for (int i = 1; i <= n; i++) dp[i] = max(dp[i - 1] + num[i], num[i]);
	maxx = dp[1];
	for (int i = 2; i <= n; i++) maxx = max(maxx, dp[i]);
	printf("%d\n", maxx);
	return 0;
}