문제 정보 Leet Code 문제 링크 난이도 : Easy 해결 방법 이전에 풀었던 문제 중 #121. Best Time to Buy and Sell Stock 을 카데인 알고리즘 (Dynamic Programming) 으로 풀었을 때와 동일한 문제였습니다. dp[i] 를 i 번째 인덱스를 가장 오른쪽 끝으로 하는 subArray 의 최대값으로 정의 후 구현하면 기존 dp[i - 1] 에 현재 값인 nums[i] 를 더하거나 혹은 nums[i] 로 subArray 를 시작하는 경우로 나눌 수 있습니다. 이렇게 풀이할 경우 nums 의 길이만큼 for loop 를 1회 수행하므로 시간복잡도는 O(n) 이 됩니다. Follow up: If you have figured out the O(n) solution..

문제 정보 Leet Code 문제 링크 난이도 : easy 해결 방법 첫 시도에는 단순히 이중 for loop 를 사용하여 O(n^2) 의 시간이 걸리게 구현하니 Time Limit Exceeded 을 판정되었습니다. 두 번째 시도에서는 prices 를 두번 순회하지 않기 위해 고민을 하던 중에 변화량을 기록하는 diff 라는 Array 를 만들고 최대 부분합을 구할 수 있는 Dynamic Programming 을 사용하여 값을 구했습니다. ( 참고로, 최대 부분합을 구하는 이 알고리즘을 카데인 알고리즘이라고 한다고 합니다. 기존 DP 와 내용은 같긴한데... 자주 등장하기 때문에 그런것 같습니다. ) 이렇게 풀고 나서 Solution 탭을 확인해보니 for loop 마다 minPrice 와 maxPro..