카데인(Kadane's)알고리즘이란

• 주어진 수열에서 가장 큰 연속 부분 배열의 합을 효율적으로 찾는 알고리즘으로 동적 프로그래밍(Dynamic Programming)의 한 예로, 지역적 최적해를 활용해 전역적 최적해를 찾는 방식

---

첫 번째 방법

접근법

변수 maxSoFar = 0, maxEndingHere = 0;
1. 각 요소에 대해 반복
2. maxEndingHere에 현재 요소를 더함
3. 만약 maxEndingHere가 음수이면 maxEndingHere = 0; (부분 배열을 새로 시작)
4. 만약 maxEndingHere가 maxSoFar보다 크면 maxSoFar = maxEndingHere; (최대 합 갱신)
5. 최종 maxSoFar 반환

---

두 번째 방법

접근법

변수 maxSoFar = arr[0], maxEndingHere = arr[0];
1. 각 요소에 대해 반복
2. 각 반복에서 maxEndingHere에 arr[i]를 더하고, 이 값이 arr[i]보다 작으면
   maxEndingHere를 arr[i]로 재설정
3. maxSoFar와 maxEndingHere 중 더 큰 값을 maxSoFar로 갱신
4. 최종 maxSoFar 반환