BOJ 1912 연속합

https://www.acmicpc.net/problem/1912
시간 1초, 메모리 128MB
input :

• n (1 ≤ n ≤ 100,000)
• n개의 수 (-1,000 <= 수 <= 1,000)

output :

• 답을 출력

조건 :

• 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합(단, 수는 한 개 이상 선택)
• ex ) {10, -4, 3, 1, 5, 6, -35, 12, 21, -1} 이라는 수열. 정답은 12+21인 33

---

시간 복잡도가 문제긴 한데... 이중 반복문 해서

i를 인제 체크 하려는 수열의 길이
j는 수열의 시작하는 지점.

으로 구성해서 계산을 하면 되지 않을까?

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
ret = -999999999

for i in range(1, n):
    for j in range(n):
        if j + i > n:
            continue
        ret = max(ret, sum(data[j : j + i]))

print(ret)

그러면 어떻게 해야 하나...

연속적.

수열의 경우 고르는 숫자들 모두 연속적으로 붙어있다.

그러면 다음 숫자를 만날 경우 두 가지 경우의 수가 발생.

1. sum(현재까지 합) + current
2. current

1번과 같이 합한 경우가 큰지. 아니면 자기 혼자가 큰지 비교를 한 후
ret 리스트에 저장을 하자.

리스트에 저장을 하면. 어느 idx에서 최댓값을 가지고 있는지 알 수 있어서 마지막에 이를 출력해주면 된다.

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
ret = [data[0]]

for i in range(1, n):
    ret.append(max(ret[i - 1] + data[i], data[i]))

print(max(ret))

현재까지의 합의 경우 ret[i - 1]에 존재하기 때문에 꺼내 쓰자.
오늘도 하나 배워갑니다...