[BOJ/C++]1912번 연속합

1912번: 연속합

---

문제

크기가 n인 정수 배열에서 연속된 수의 합이 가장 큰 값을 출력하라.

 

풀이

i번까지의 연속 수 합이 가장 큰 dp[i]를 이용해  다이나믹 프로그래밍으로 푼다.

dp[i]는 dp[i-1]+arr[i]와(i-1번째까지 연속 수 합이 가장 큰 수+i번째 배열의 수) arr[i]를 비교해 더 큰 값이 dp[i]에 들어간다.

 

소스코드

#include<iostream>
using namespace std;

int main(void){
    int n;cin>>n;
    int arr[n+1];
    for(int i=1;i<=n;i++)
        cin>>arr[i];
    
    int dp[n+1]; dp[0]=0;
    int max_num=-1000;
    for(int i=1;i<=n;i++){
        dp[i]=max(dp[i-1]+arr[i],arr[i]);
        max_num=max(max_num,dp[i]);
    }
    cout<<max_num<<endl;
}