[백준] 1912.cpp : 연속합

www.acmicpc.net/problem/1912

1912번: 연속합

---

• 음수가 껴있더라도 해당 위치까지의 누적합이 양수일 경우, 최댓값을 이어나갈 수 있다.
• 입력받은 값들을 계속 더해나가면서, 합이 음수가 될 때만 초기화시켜주면 가장 큰 합을 구할 수 있다.
• 위의 내용에 해당하는 구간들이 여러 군데가 있을 수 있기 때문에, 최댓값 갱신에도 신경을 써줘야 한다.

---

#include <iostream>

using namespace std;

int n, answer = -1000, maxi;

int main(void)
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> n;
    for(int i = 1, temp ; i <= n ; i++)
    {
        cin >> temp;
        if(maxi < 0) maxi = temp;           // 직전까지의 합이 0보다 작으면 최댓값 다시 누적
        else         maxi = maxi + temp;    // 그 외의 경우 최댓값에서 계속 더해나감
        if(maxi > answer) answer = maxi;    // 최댓값 갱신은 필요시에만
    }
    cout << answer << endl;
}