Algorithm LSCS

문제

정수를 요소로 갖는 배열을 입력받아 다음의 조건을 만족하는 LSCS를 리턴.

• LSCS : 주어진 배열의 연속된 부분 배열*의 합을 구한다고 할 때, 이 중 가장 큰 값(Largest Sum of Contiguous Subarray)
• 연속된 부분 배열 : 배열 [1, 2, 3]의 연속된 배열은 [1], [1, 2], [1, 2, 3], [2], [2, 3], [3]

인자

• number 타입을 요소로 갖는 배열
• arr.length는 60,000 이하
• arr[i]는 -100,000 이상 100,000 이하 정수

주의사항

• 배열의 모든 요소가 음수인 경우도 있다.

멱집합이 아닌 연속된 배열!!

카데인 알고리즘으로 풀 수 있다.

const LSCS = function (arr) {
    let maxSum = -100000
    let currentSum = 0

    for(let i = 0; i < arr.length; i++){ 
      currentSum = Math.max(arr[i], currentSum + arr[i])
      maxSum = Math.max(currentSum, maxSum)  
    }
    return maxSum
};