링크 : www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
#include <iostream>
using namespace std;
int max(int a, int b) { return a > b ? a : b; }
int arr[100001];
int sum[100001];
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n = 0, maxi = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
sum[i] = arr[i];
}
maxi = sum[0];
for (int i = 1; i < n; i++) {
sum[i] = max(arr[i], sum[i - 1] + sum[i]);
if (maxi < sum[i]) maxi = sum[i];
}
cout << maxi << "\n";
return 0;
}
DP는 복잡하게 생각하면 오히려 잘 안풀리는 유형인 것 같다.

'🖥️ CS > Baekjoon Algorithms' 카테고리의 다른 글
#11047번 동전 0 (C++) (0) | 2020.10.28 |
---|---|
#2583번 영역구하기 (C++) (0) | 2020.10.20 |
#11053번 가장 긴 증가하는 부분 수열 (C++) (0) | 2020.10.20 |
#2156번 포도주 시식 (C++) (0) | 2020.10.16 |
#10844번 쉬운 계단 수 (C++) (0) | 2020.10.15 |