Kadane의 알고리즘을 사용하여 JavaScript에서 하위 배열의 최대 합 찾기

문제

첫 번째이자 유일한 인수로 정수 배열(양수 및 음수 모두), arr을 취하는 JavaScript 함수를 작성해야 합니다.

우리의 함수는 선형 시간에서 모든 하위 배열의 최대 합계를 반환해야 합니다.

임의의 인덱스 i에서 local_maximum은 arr[i]의 최대값이고 인덱스 i에서 arr[i]와 local_maximum의 합 - 1입니다.

이것이 선형 시간에서 배열 내의 최대 하위 배열 합계를 찾기 위해 적용할 것입니다.

예를 들어, 함수에 대한 입력이 -

입력

상수 arr =[-2, 1, -3, 4, -1, 2, 1, -5, 4];

출력

상수 출력 =6;

출력 설명

최대 합계가 있는 하위 배열은 -

[4, -1, 2, 1]

예시

다음은 코드입니다 -

 const arr =[-2, 1, -3, 4, -1, 2, 1, -5, 4]; const maxSequence =(arr =[]) => { let currentSum =0 let maxSum =0 for(arr의 요소) { const nextSum =currentSum + 요소 maxSum =Math.max(maxSum, nextSum) currentSum =Math.max(nextSum, 0) } return maxSum};console.log(maxSequence(arr)); 
출력
 
6