Kadane 알고리즘

입력받은 정수배열의 하위배열에 있는 모든 정수를 합산하여 얻을 수 있는 최대 합계를 반환하는 함수를 작성합니다. 하위배열에는 인접한 숫자(입력 배열에서 바로 옆 숫자)만 포함되어야 합니다.

예제 1

입력

arr = [
  3, 5, -9, 1, 3, 
  -2, 3, 4, 7, 2, 
  -9, 6, 3, 1, -5, 
  4
]

출력

19 
// [1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1]