알고리즘 관련/BOJ
1912 연속합
Andrew-Yun
2020. 12. 14. 22:43
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
고민을 많이 한 문제였는데, 놓친 부분은 다음과 같다.
1. 부분합이 음수가 될 수 있음
2. 부분합 < 0이면, 현재 원소가 가장 큰 부분합
점화식을 세우는게 어렵구나.. 추론이 부족한듯하다.
#include <iostream>
#include <algorithm>
using namespace std;
int arr[100001] = { 0, };
int dp[100001] = { 0, };
int N;
int main()
{
int result = 0;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
dp[0] = arr[0];
result = dp[0];
for (int i = 1; i < N; i++) {
dp[i] = max(dp[i - 1] + arr[i], arr[i]);
result = max(dp[i], result);
}
printf("%d\n", result);
return 0;
}