DP

[알고리즘] Kadane’s(카데인) Algorithm - Array에서 부분합의 최대 찾기

요즘 매일 leetcode daily 문제를 풀고 있다. 생각보다 동기부여가 잘 되어서 너무 좋다! 오늘은 Dynamic Programming 알고리즘의 일종인 Kadane’s(카데인) Algorithm에 대해 포스팅해보고자 한다. Dynamic programming은 문제를 sub problems로 나누어, sub problem을 그 다음 step의 답을 구하는데에 계속해서 저장해놓고 이용하는 개념이다. # Kadane's Algorithm? 일단 이 알고리즘은 숫자 Array가 주어졌을 때, 이 array 내 연속된 subset 원소들의 합 중 가장 max인 값을 반환하는 알고리즘이다. 문제를 예로 들면 이렇다. 주어진 배열 A를 [1,-2,3,5,-4,2,5] 라고 했을 때 Maximum Subar..