[백준 1912] 연속 합 (C++/Python)

n의 크기가 1<= n <= 100,000이고 시간제한이 1초이기 때문에 N^2처럼 이중포문을 돌려 비교할 수는 없다.

O(N)이나 O(NlogN) 안에 풀어야하고 나는 숫자를 입력 받음과 동시에 이전 부분집합의 합들과 비교하면서 최대값을 갱신하는 방법으로 풀었다. 알고리즘은 DP로 분류되어 있긴한데 굳이 배열 만들어서 저장 안하고 변수 하나로 비교해가면서 풀어도 될 듯.

 

---

 

C++)

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

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

	int n, temp;
	cin >> n;

	int sum = 0;
	int ans = -1111;

	for (int i = 0; i < n; i++) {
		cin >> temp;

		sum = max(sum + temp, temp);
        ans = max(ans, sum);
	}
	
	cout << ans;

	return 0;
}

 

 

 

Python)

import sys

read = sys.stdin.readline

n = int(read().rstrip())
arr = list(map(int, read().rstrip().split()))

ans = -1111
sum = 0

for ele in arr:
    sum = max(sum+ele, ele)
    ans = max(sum, ans)

print(ans)