[알고리즘/DP] 백준 1912번: 연속합 - C++

www.acmicpc.net/problem/1912

1912번: 연속합

다이나믹 프로그래밍(DP) 을 이용하였다

 

#include <iostream>
#include <algorithm>
using namespace std;

int a[100000], d[100000];

int main() {
	int n, ans;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	d[0] = a[0];
	for (int i = 0; i < n; i++) {
		d[i] = max(a[i], d[i - 1] + a[i]);
	}
	ans = d[0];
	for (int i = 0; i < n; i++) {
		ans = max(ans, d[i]);
	}
	cout << ans << endl;
}

 

github.com/waves123/1912/blob/master/1912/1912.cpp

waves123/1912

 

다이나밍 프로그래밍 문제

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 1912번: 연속합 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 11055번: 가장 큰 증가 부분 수열 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 11052번: 카드 구매하기 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 9095번: 1,2,3 더하기 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 11726번: 2xn 타일링 - C++

2020/12/12 - [알고리즘] - [알고리즘/DP] 백준 1463번: 1로 만들기 - C++