문제링크: https://www.acmicpc.net/problem/1912
#include<bits/stdc++.h>
using namespace std;
#define mine
int N;
int a[100001];
int dp[100001];
int main(){
ios_base::sync_with_stdio(false);
// freopen("../input.txt","rt",stdin);
cin >> N;
for(int i=1; i<=N; i++){
cin >> a[i];
}
memset(dp, 0, sizeof(dp));
int res = -987654321;
for(int i=1; i<=N; i++){
// 핵심부분이다.
// 계속 더해주되, 현재 값과 지금까지의 값중 더한 것 중에 더 큰것을 dp에 저장시켜준다.
// 이 방법 기억해두도록 하자
dp[i] = max(dp[i-1]+a[i], a[i]);
res = max(dp[i], res);
}
cout<<res<<endl;
return 0;
}
지금까지 단순히 DP문제들은 대부분 재귀로 해결하려고하였지만, 이렇게 반복문으로 손쉽게 사용할 수 있다는 것을 배웠다. 또한 연속합 문제는 이런식으로 풀어야겠다는 풀이과정을 잘 복습해야겠다.