[백준/1912] 연속합 | 누적합 | max의 활용

https://www.acmicpc.net/problem/1912

1912번: 연속합

[알고리즘]

처음에 이 문제를 보고 이중 for문의 인덱스를 i를 기준으로 띄워가면서 누적합을 통해 결과를 도출하려고 했다. 

n=int(input())
li = list(map(int, input().split()))

total = 0
ans=[]

for i in range(n):
    total = 0
    for j in range(i,n):
        total+=li[j]
        ans.append(total)
          
print(max(ans))

 

예상은 했지만 메모리 초과,, total 변수가 갱신될 때마다 리스트에 넣어줘야 하니까 당연한 결과다ㅜ_ㅜ

그래서 리스트 안쓰고 변수 쓰자!해서 쓴 코드가 아래와 같다.

n=int(input())
li=list(map(int, input().split()))

total=0
ans=0

for i in range(n):
    total=0
    for j in range(i,n):
        total+=li[j]
        ans=max(ans,total)
          
print(ans)

이렇게 하면 시간 초과가 뜬다..

n의 범위가 100,000이니까 당연함ㅇㅇ 

그래서 과감하게 이중 for문 풀이는 버리고 다른 분 코드를 봤다.

---

[최종코드]

n=int(input())
li = list(map(int, input().split()))

for i in range(1,n):
    li[i]=max(li[i], li[i-1]+li[i])

print(max(li))

리스트 값을 수정하면서 max를 지정해주면 리스트 내부에서 누적값을 저장하면서 낭비없이 연산을 수행할 수 있다. 내가 쓴 코드는 브루트포스와 비슷한 풀이기 때문에 메모리/시간 초과가 나는 것

 

-핥짝님이 리뷰해주신 코드-

'''약간 그리디로 풀어봤씀다! 더해가다가 0 미만이면 그 이전까지는 버리는게 이득이라는 규칙으루
매번 0 미만이면 0으로 초기화하는(현재값을 더하지 않고 그 이전 부분을 버림) 방식입니다.
전부 음수였다면 max(li)를 출력해주구요.
결국 작성하신 DP 코드와 비슷한 방식인데, 시간복잡도는 동일하고 메모리 복잡도를 좀 더 줄여봤어요'''

n = int(input())
li = list(map(int, input().split()))

tmp = 0
ans = -1001
for cur in li:
    tmp += cur
    if tmp < 0:
        tmp = 0
    else:
        ans = max(ans, tmp)

if ans == -1001:
    print(max(li))
else:
    print(ans)