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

분석 및 후기

일단 내가 아직 잘 DP를 잘 못푸는 거같다고 다시한번 생각하게됨.. 시간도 많았는데 결국 못품...

max함수와 캐시질을 같이 활용을 어떻게 해야하는지 감이 안잡혀있는거 같다라고 느낌.

특히

cache[i] = max(cache[i-1] + arr[i], arr[i])

이런 코드 보면은 바로 아~~... 하면서 이해를 하는데 혼자서는 그생각을 계속 못하는게 부족한 점인거 같음..

cpp코드

#include <iostream>
using namespace std;

#define MAX 100001
#define endl "\n"

int cache[MAX];
int arr[MAX];

int main()
{	
	int n;
	cin >> n;
	
	for (int i = 1; i <= n; ++i) cin >> arr[i];

	cache[1] = arr[1];

	int Max = -1001;
	for (int i = 1; i <= n; ++i)
	{
		cache[i] = max(cache[i - 1] + arr[i], arr[i]);
		Max = max(Max, cache[i]);
	}

	cout << Max;

	return 0;
}