[백준 10211번] Maximum Subarray (C++)

문제링크 : https://www.acmicpc.net/problem/10211

10211번: Maximum Subarray

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[1001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int T, N;
    cin >> T;
    while(T--)
    {
        cin >> N;
        for(int i=0; i<N; i++)
        {
            cin >> arr[i];
        }

        int sum=0, maxV=-1001; 
        for(int i=0; i<N; i++)
        {
            for(int j=i; j<N; j++)
            {
                sum+=arr[j]; //누적합
                maxV=max(maxV, sum); //누적합 최대
            }
            sum=0;
        }
        cout << maxV <<"\n";
    }
    
    return 0;
}

누적합 문제이다.

여기서 주의해야할 것은 누적합에 음수가 들어간다는 점이다.

 

따라서 최대값을 저장할 변수를 -1001로 초기화해줬다. (주어지는 수가 절댓값이 1000보다 작은 정수이기 때문)

그리고 음수를 더하는 경우가 있으므로 최대값 갱신을 2번째 for문 안에서 해줘야 한다.

그러고 나서 누적합 부분을 초기화해주고 다시 탐색해준다.