[dp/백준] 1912번: 연속합(2차)

-문제: https://www.acmicpc.net/problem/1912

 

-정답풀이:

(max(dp[i]+data[i+1],data[i+1])): 이 식은 값을 누적했을 때와, 새로 시작했을 때의 값 중에 최댓값을 dp에 저장한다 

n=int(input())
data=list(map(int,input().split()))
dp=[data[0]]
for i in range(n-1):
    dp.append(max(dp[i]+data[i+1],data[i+1]))
print(max(dp))

-메모리 초과 

nxn dp 행렬에서 i번째 시작해서 j번째 까지의 합을 모두 구해서 

각 행에서 최댓값을 찾고, 그 중에서 최댓값을 찾으면 된다고 생각했는데 

메모리가 128MB라서 메모리 초과가 난 것 같다 

n=int(input())
data=list(map(int,input().split()))
dp=[[0]*n for _ in range(n)]
for i in range(n):
    dp[i][0]=data[i]
    for j in range(1,n):
        dp[i][j]= dp[i][j-1]+data[j]
        
answer=0
for i in range(n):
    answer=max(answer,dp[i])
    
print(answer)