일단 내가 아직 잘 DP를 잘 못푸는 거같다고 다시한번 생각하게됨.. 시간도 많았는데 결국 못품...
max함수와 캐시질을 같이 활용을 어떻게 해야하는지 감이 안잡혀있는거 같다라고 느낌.
특히
cache[i] = max(cache[i-1] + arr[i], arr[i])
이런 코드 보면은 바로 아~~... 하면서 이해를 하는데 혼자서는 그생각을 계속 못하는게 부족한 점인거 같음..
#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;
}