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

문제

10211번: Maximum Subarray

 

코드

#include <iostream>
#include <algorithm>

int dp[1001],arr[1001];
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int T; cin>>T;
    while(T--){
        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(dp[i-1]+arr[i],arr[i]);
            ans = max(dp[i],ans);
        }
        cout<<ans<<'\n';
    }
}

 

풀이

배열의 연속적인 원소들의 부분집합에서 가장 큰 값을 찾아내면 됩니다. 따로 크게 설명할 부분은 없기에 조건문만 잘 살펴보면 될 것 같습니다.