[코드업] 3705 - 연속된 구간의 최대합

어떤 수열이 있을 때 연속된 구간의 최대합을 출력하려고 한다.

예를 들어

2 -6 4 5 -2 6 2 -1이라는 수열이 있다면 

연속된 구간의 최대 부분합은 15이다. (4+5+ -2 + 6 + 2)

입력 예시  

8
2 -6 4 5 -2 6 2 -1

출력 예시

15

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
	int N;
	cin >> N;

	int sum = 0;
	int ret = -987654321;

	int num;
	for(int i = 0; i < N; i++){
		cin >> num;
		sum += num;
		ret = max(ret, sum);
		if(sum < 0) sum = 0;
	}

	cout << ret;

	return 0;
}