연속된 부분 배열 최대합 구하기, Javascript

문제

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

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

주의사항

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

입출력 예시

let output = LSCS([1, 2, 3]);
console.log(output); // --> 6

output = LSCS([1, 2, 3, -4]);
console.log(output); // --> 6 ([1, 2, 3])

LSCS([1, 2, 3, -4, 5]);
console.log(output); // --> 7 ([1, 2, 3, -4, 5])

LSCS([10, -11, 11]);
console.log(output); // --> 11 ([11])

풀이 코드

const LSCS = function (arr) {
	let result = -Infinity;
    let max = 0;
    
    for(let i = 0; i < arr.length; i++){
    	max = Math.max(arr[i], max + arr[i]);
        result = Math.max(max, result);
    }
    
    return result;
};

연속된 이라는 단어에 초점을 맞춰야 합니다.
ex) output = LSCS([1, 2, 3, -4]);
arr[0] = 1 입니다.
따라서 max = 1 됩니다.
arr[1] = 2 입니다.
arr1 와 max + arr[1] (1 + 2)
비교하면 max는 3이 됩니다.

arr[2] = 3 입니다.
arr2 과 max(현재값 3) + arr2 더하면 6이고, max는 6 이 됩니다.
(Math.max 모르시면 큰일..)

arr[3] = -4 입니다.
arr[3] = -4 와 max(현재값 6) + arr3를 더하면 2가 됩니다.

반복하면서 result에는 6이 담겨있는 상태입니다.

따라서 최대값 6을 출력하게 됩니다.

흐름을 파악하면 쉽게 풀 수 있는 문제입니다..지만 생각하기 까지 어려웠습니다.
(for문 돌리면 시간 초과 나와요..)