카데인 알고리즘이란? 참고: sustainable-dev.tistory.com/23 DP 기법 중 하나이다. 앞의 값을 이용해 뒤의 값을 구할 수 있다. 최대 부분 합을 구할 때 사용한다. 1차원 배열에서 부분 배열 중 최대 합을 구하면된다. 핵심코드 for (int i = 0; i < N; i++) { sum = Math.max(arr[i], sum + arr[i]); max = Math.max(sum, max); } A[5]까지 부분합은 A[4]의 부분합을 통해서 구할 수 있다. A[4]의 Sum을 보면, [-1, 3, 0, 1, -1]이라는 값이 있다. 그 다음 A[5]의 Sum을 보면 [1, 5, 2, 3, 1]이 있는데, 이 값들은 이전 A[4]의 배열에서 A[5]의 값인 2를 더해준 값이다. ..
