다이나믹 프로그래밍

문제 풀이 내 풀이 import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) dp = [0] * n dp[0] = arr[0] for i in range(1, len(arr)): dp[i] = max(dp[i-1] + arr[i], arr[i]) print(max(dp)) 이 문제는 단순하게 생각하여 현재까지 합들보다 현재 값이 크면 시작점을 현재 인덱스로 바꾸면 해결되는 문제이다. 이 문제에선 다음을 고려하여 풀이를 진행하면 해결법이 생각날 것이다. 음수 값이 포함되어도 합이 최대 일 수 있다는 점 그렇지만 음수는 합에 영향을 준다는 점 (모두 0 이상인 수라면 전체 합이 최대이다) 한 번 다음 ..