[ BOJ 백준 1912번 - 연속합 ] 해설 및 코드

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

 

목적

n개의 정수 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하자.

 

접근법

1. s[i]를 a배열의 i번째 원소를 끝으로 하는 최대 연속합이라고 정의할 때, s[i]는 a[i] + max(s[i-1], 0)이다. 

 

2. 최종적으로 구하고자 하는 것은 s[1] ~ s[n]중 최대 값이다.

 

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,ans,prev,curr;
    cin>>n>>ans;
    prev=ans;
    while(--n){
        int num;cin>>num;
        curr=num+max(prev,0);
        prev=curr;
        ans=max(ans,curr);
    }
    cout<<ans;
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.