[DP] boj 1912 - 연속합

백준 1912는 판단할 값을 입력 배열과 index를 맞춘 배열로 저장해서 해결한다. 참고 링크

방식은 같은데 속도가 더 빠른 풀이를 발견했다. 변수를 하나 없앴고 배열을 초기화하는 방법이 다르다. 참고 링크

성공한 방법

import sys

n = int(sys.stdin.readline())
inputArr = list(map(int, sys.stdin.readline().split(' ')))
temp = [0 for _ in range(n)]
maxVal = -1001

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

print(maxVal)

---

실패한 방법

시간 초과 - O(n^2) 참고 링크

import sys

n = int(sys.stdin.readline())   # 수열의 원소 개수
inputArr = list(map(int, sys.stdin.readline().split(' ')))

def checkSum(num):
    tempSum = inputArr[num]
    tempArr = []
    tempArr.append(tempSum)

    for i in range(num+1, n):
        tempSum += inputArr[i]
        tempArr.append(tempSum)

    return max(tempArr)

sumArr = [checkSum(i) for i in range(n)]
print(max(sumArr))