문제 : LSCS

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

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

문제의 접근

솔직히 생각나는 방법은 모든 멱집합을 구해서 각 값의 합을 구하는 방법이 제일 먼저 생각 났지만 이는 알고리즘의 효율을 매우 저해한다. 그래서 구글링을 통해서 조금 괜찮은 방법을 찾아보았다.

const LSCS = function (arr) {
  //TODO: 여기에 코드를 작성합니다.
  let max = -1000000
  let sum = 0;
  for(let i = 0; i < arr.length; i++) {
    sum = sum + arr[i];
    if(sum > max) {
      max = sum;
    }
    if(sum < 0) {
      sum = 0;
    }
  }
  return max;
};

이건 논리를 생각하면 생각해낼 수 있었을지 모른다. 계속해서 수를 더하다가 음수가 더해지면 그 수는 분명 음수가 더해지기 전까지의 값만이 최대값일 것이다.

음수가 더해지면 그 수는 더 이상 최대값이 아니고 더하기 전의 값이 최대값이다.

때문에 음수가 나오기 전까지의 수를 더한 값이 최대값이 되기 때문에 max에 할당해주고 음수가 나오면 합을 다시 0으로 만들어준뒤 값을 계속 더해나간다. 이를 for문 한번으로 구한다면 이는 복잡도가 O(n)이 될 것이다.

Advanced

LSCS를 계산하는 효율적인 알고리즘(O(N))이 존재합니다. 쉽지 않기 때문에 바로 레퍼런스 코드를 보고 이해하는 데 집중하시기 바랍니다.

한번에 해결했다.

문제를 통해 생각해 볼 것

저번 문제도 그렇고 어렵다고 레퍼런스 보라고한 문제는 생각보다 그렇지 않다. 오히려 그렇지 않은 문제들이 더 어려운듯 하다. 그리고 이 문제도 조금만 더 생각했다면 충분히 혼자 풀 수 있지 않았을까 생각한다.

// 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;
// };

// dynamic programming: O(N)
const LSCS = function (arr) {
  let subArrSum = 0; // 연속 배열의 합
  let max = Number.MIN_SAFE_INTEGER; // 정답의 후보를 저장
  for (let i = 0; i < arr.length; i++) {
    subArrSum = subArrSum + arr[i];
    if (subArrSum > max) max = subArrSum;

    // 연속된 구간의 합이 음수인 경우,
    // 해당 부분은 버리고 다시 시작해도 된다.
    if (subArrSum < 0) {
      subArrSum = 0;
    }
  }

  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;
// };