자료구조 - 배열 문제 : 가장 큰 부분합 구하기

연습문제 : 가장 큰 부분합 구하기

정수들의 리스트가 입력으로 들어옴. 이 정수들의 리스트를 일부분만 잘라내어 모두 더했을 때의 값을 부분합이라 부름. 이때 가장 큰 부분합을 구해봐.

예를 들어, [-10, -7, 5, -7, 10, 5, -2, 17, -25, 1]이 입력으로 들어왔다면 [10, 5, -2, 17]을 모두 더한 30이 정답.

※입력에는 최소 하나 이상의 양수가 존재.

※이 문제에는 여러 종류의 풀이법이 존재. 각 풀이법의 시간 복잡도를 고려하면서 여러가지 방법으로 문제를 풀어봐.

def maxSubArray(nums):
    return 0

def main():
    print(maxSubArray([-10, -7, 5, -7, 10, 5, -2, 17, -25, 1])) # 30이 리턴되어야 합니다

if __name__ == "__main__":
    main()

 

>>>

def maxSubArray(nums):

    cache = [None] * len(nums)
    cache[0] = nums[0]
    for i in range(1, len(nums)):
        cache[i] = max(0, cache[i-1]) + nums[i]
    return max(cache)