3705 : 연속된 구간의 최대합

문제

연속된 구간의 최대합

 

코드

#include <iostream>
using namespace std;
 
 
int dp[100001];
int arr[100001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N; cin>>N;
    
    for(int i=0; i<N; i++){
        cin>>arr[i];
    }
    
    int ans=arr[0];
    dp[0]=arr[0];
    for(int i=1;i<N; i++){
        dp[i]=max(arr[i],dp[i-1]+arr[i]);
        ans=max(ans,dp[i]);
    }
    cout<<ans;
}

 

풀이

이전에 한번 백준에서 유사한 문제를 푼 적이 있어서 간단하게 해결한 문제였습니다.

[백준,c++] 10211번 - Maximum Subarray

여기 위 문제와 동일합니다.

 

채점