Algorithm problem-26

1. 문제

• 정수를 요소로 갖는 배열의 연속된 부분 배열의 집합 중 요소들의 합이 가장 큰 값을 내는 경우(LSCS)의 합을 리턴

2. 시도

• 처음에 연속된 값으로 이루어진 배열을 멱집합으로 착각하여 문제를 풀었음
• 멱집합 중 가장 큰 수를 이루는 값의 합을 리턴시켜야 함
• 멱집합을 구할 때, 요소를 푸쉬하는게 아니라 +시켜주면 어떨까
• 아니면, 멱집합을 구하고 모든 요소를 다 더해서 새로운 배열로 만들어야겠다
• 그 배열의 Math.max 리턴
• 연속 배열의 합 중 가장 큰 합은 반복문을 통하여 다 구해보면 된다
• 0부터 끝까지 다 더해보고, 그 중 큰 값이면 갱신시키는 방식으로
• Number.MIN_SAFE_INTEGER(JS에서 안전하게 사용 가능 한 제일 작은 음수)

3. 수도코드

const LSCS = function (arr) {
  // 가장 큰 값을 더해줄 변수를 하나 선언, 음수로만 이루어졌을 수도 있기에
  // 임의의 값(0)이 아닌 배열의 첫 요소로 임의의 값을 선언
  let max = arr[0];
  // 0번부터 모든 수를 다 더해보고 최대값 변수와 비교해서 더 크다면 저장해서 갱신
  for (let i = 0; i < arr.length; i++) {
    // 모든 시작값을 다 더해봐야 하기 때문에 시작값을 항상 비교
    let sumArr = arr[i];
    if (max < sumArr) {max = sumArr;}
    // 시작값부터 뒤에 배열의 모든 값을 하나씩 더해가며 비교해 본다
    for (let j = i + 1; j < arr.length; j++) {
      sumArr = sumArr + arr[j];
      if (max < sumArr) {max = sumArr;}
    }
  }
  return max;
}

4. 레퍼런스

// 모든 배열이 음수인 경우, 배열의 요소 중 가장 작은 음수 하나가 가장 큰 수일 것
// 연속된 구간의 합이 음수인 경우, 배제하고 봐도 무방하다
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;
};