연속 부분 배열

- 문제:

정수를 요소로 갖는 배열을 입력받아 다음의 조건을 만족하는 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])

- 주의:

효율적인 알고리즘(O(N))으로 해결해야 합니다.

- 풀이:

여러 해결 방식이 있겠지만, 주어진 배열의 요소를 요소의 길이만큼만 조회를 하는 방법을 찾아야 한다.
만약 배열의 첫 요소부터 시작해서 모든 부분 배열을 돌아가려면 이중 반복문을 피할 수 없다. 또는 재귀를 사용할 수 밖에 없을 것이다. 하지만 이 방식으로는 문제를 O(N)으로 해결하기 어렵다.

배열의 요소의 수 중에 음수가 없다면, 가장 큰 부분 배열의 합은 배열 모든 요소의 합일 것이다. 그러나 우리는 음수를 고려해야한다.

1) 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;
}

문제 조건에서 제시한 최소값을 먼저 max로 지정했다. 모든 부분 배열을 돌기위해 0번째 인덱스에서부터 시작해서 마지막 인덱스까지, 배열의 요소마다 반복문을 다시 돌리면서 max 값을 새로 할당했다.

2) O(N) 풀이 방식

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

연속된 구간의 배열의 합이 음수로 나오는 경우, 해당 구간 이후부터 다시 시작할 수 있는 점을 기억하자.
특정 구간의 요소가 아무리 크다고 하더라도 특정 연속 구간의 합이 음수일 경우 최대합를 다시 다음 수부터 확인해야 할 것이다.
부분 배열의 어떤 특정 구간의 집합이다. 해당 특정 구간의 합이 음수가 나올 경우, 해당 값을 버리고 다음 수부터의 구간의 합을 구해보고, 음수가 나오기 전까지의 max와 비교해서 max를 구하는 것이다.

3) DP 풀이 방식
이 방법은 다른 블로그에서 참조한 것이다.
왜 해당 방법이 DP일 수 있을지 고민한 결과, (정확하지 않지만) memoization 방식을 활용해서 DP 알고리즘으로 푼 것이 아닐까 싶다.

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

- 마무리:

LSCS...막막했다.
이번 풀이를 통해, 최대한 발생할 수 있는 가정을 세워보고 문제를 풀어야겠다 생각이 들었다.
수도 코드를 적는 스킬의 개선이 필요했다.
문제를 나눌 수 있을 때까지 나누어 보는 습관을 더욱 키워야 겠다.