미국 개발자 산만한 일기 미국 개발자 산만한 일기

관련 문제 링크 : leetcode.com/problems/maximum-subarray/ leetcode.com/problems/gas-station/ 다른 다이나믹 프로그래밍 문제 : 더보기 leetcode.com/problems/best-time-to-buy-and-sell-stock/ 이문제의 핵심은 각각의 부분합을 구할 때 현재 위치 이전까지의 결과가 반영된다는 것을 이해하는 것이다. 예를들어 -3이 있는 index 2까지의 부분합을 구할 때 우리는 이전 index 들인 -2 와 1 의 합에 현재 index 2의 값 -3을 더함으로써 쉽게 index 2 까지의 부분합을 구할 수 있다. 그리고 그다음 index인 4까지의 부분합을 구할 때 또 -3까지의 부분합에 4를 더하여 쉽게 구할 수 있다. ..