JavaScript Algorithm - LSCS(Largest Sum of Contiguous Subarray)

문제 설명 : 

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

• LSCS: 주어진 배열의 연속된 부분 배열*의 합을 구한다고 할 때, 이 중 가장 큰 값(Largest Sum of Contiguous Subarray)
• 연속된 부분 배열들: 배열 [1,2,3]의 연속 부분 배열은 [1], [1, 2], [1, 2, 3], [2], [2, 3], [3] 입니다.
• 입출력 예시를 보면 이해하시기 좀 더 편합니다. 

 

입력

인자 1 : arr

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

출력

• number 타입을 리턴해야 합니다.

주의사항

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

입출력 예시

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])

 

A . [1, 2, 3] 의 배열 중 연속된 배열 합을 구한다고 할 때 가장 큰 값은 1 + 2 + 3 =6입니다.

B.  [1, 2, 3, -4]의 배열 중 연속된 배열 합을 구한다고 할 때 가장 큰 값은 1 + 2 + 3  = 6입니다. 

C. [1, 2, 3, -4, 5]의 배열 중 연속된 배열 합을 구한다고 할 때 가장 큰 값은 1 + 2 + 3 -4 +5 = 7입니다.

D. [10, -11, 11]의 배열 중 연속된 배열 합을 구한다고 할 때 가장 큰 값은 11입니다. 

 

 

풀이 코드 

수도코드 순서 정의
1. 연속 배열의 합 변수 설정
2. 정답으로 반환할 변수 설정 이 때 JavaScript에서 안전한 최대 정수값으로 설정
3. for 문으로 배열의 길이만큼 반복 순회
4. subArrSum 변수에 연속된 배열의 합을 대입
5. subArrSum이 max 값보다 크면 max 값에 subArrSum값을 대입
6. subArrSum이 음수가 될 경우 0으로 리셋하기

7. max를 리턴하기 

 

const LSCS = function(arr){
    //연속 배열의 합
    let subArrSum = 0; 

    //정답의 후보를 저장
    //Number.MAX_SAFE_INTEGER 상수는 JavaScript에서 안전한 최대 정수값을 나타냅니다.
    let max = Number.MIN_SAFE_INTEGER 

    //max -9007199254740991
    console.log("max",max)
    
    for (let i=0; i < arr.length; i++){
        subArrSum = subArrSum + arr[i]
        //배열합이 max 보다 크면 max값에 대입
        if(subArrSum > max){
            max = subArrSum
        }
        console.log("subArrSum",subArrSum)
        //배열합이 음수인 경우 해당부분은 버리고 다시 시작
        if(subArrSum<0){
            subArrSum=0;
        }
    }

    console.log("max",max)
    return max;

}

// also dynamic 2: O(N)
// const LSCS = function (arr) {
//   let subArrSum = arr[0];
//   let max = arr[0]; // 정답의 후보를 저장
//   for (let i = 1; i < arr.length; i++) {
//     // subArrSum는 바로 직전의 요소까지 검토했을 때 가장 연속합
//     // 연속합에 추가로 검토하는 요소, 즉 arr[i]를 더하는 것보다
//     // arr[i] 하나의 값이 더 큰 경우 (subArrSum가 음수일 경우)
//     // subArrSum를 버리는 게 좋다.
//     // 쭉 더해서 음수인 부분은 굳이 더할 필요가 없다.
//     subArrSum = Math.max(subArrSum + arr[i], arr[i]);
//     max = Math.max(max, subArrSum);
//   }

//   return max;
// };

// naive solution: O(N^2)
// const LSCS = function (arr) {
//   let max = -100000;
//   for (let i = 0; i < arr.length; i++) {
//     let sum = arr[i];
//     if (sum > max) max = sum;
//     for (let j = i + 1; j < arr.length; j++) {
//       sum = sum + arr[j];
//       if (sum > max) max = sum;
//     }
//   }
//   return max;
// };

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])

 

console.log 값 출력로그

max -9007199254740991
subArrSum 1
subArrSum 3
subArrSum 6
max 6
6
max -9007199254740991
subArrSum 1
subArrSum 3
subArrSum 6
subArrSum 2
max 6
6
max -9007199254740991
subArrSum 1
subArrSum 3
subArrSum 6
subArrSum 2
subArrSum 7
max 7
6
max -9007199254740991
subArrSum 10
subArrSum -1
subArrSum 11
max 11
6