[c++][baekjoon]1912 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

[풀이]

-다이나믹 프로그래밍으로 풀수 있다. 

#include <iostream>
#define MAXN 100010
using namespace std;
int N;//입력 갯수 
int A[MAXN];//입력 데이타 저장할 배열 
int dp[MAXN];//다이나믹 프로그래밍 저장용 배열 
 
void Solve(){
    dp[1] = A[1];
    int sol = dp[1];
    for (int i = 2; i <= N; i++){
        dp[i] = max(A[i], dp[i-1] + A[i]);
        if(sol<dp[i])  sol= dp[i];
    }
    cout << sol << endl;
}
 
void InputData(){
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> A[i];
}
int main(void){
	InputData();
    Solve();
    return 0;
}

 

- dfs로 풀수 있다. 

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100010
int N;
int D[MAXN];
int max_sum=(1<<31);
void dfs(int n, int sum){
	if(n>N) return;
	max_sum=max(max(max_sum,D[n]),sum);

	if(D[n]>sum){
		sum=0;
		n--;
	}
	dfs(n+1,sum+D[n+1]);
}
void InputData(){
	cin>>N;
	for(int i=1; i<=N; i++)
		cin>>D[i];
}
int main(){
	InputData();
	dfs(1,D[1]);
	return 0;
}