Toy 문제 26

문제

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

• LSCS: 주어진 배열의 연속된 부분 배열*의 합을 구한다고 할 때, 이 중 가장 큰 값

Advanced

• LSCS를 계산하는 효율적인 알고리즘(O(N))이 존재합니다.

수도코드(해석)

2중for문을 사용하여서 해결이 가능하지만, N의2승 시간복잡도가 나오기 때문에 for문을 한번만 사용하여야 합니다.

이러한 해결을 값에 대한 비교를 한번에 2번하여 해결 가능합니다.

배열의 처음부터 시작하여 i번 째 인자 하나하나를 더해주면서 Math.max 를 이용하여 큰 값을 result에 담아주는 방식 입니다.

 

두개의 변수를 만들어 주어서 arr[0]을 담아놓습니다.

반복문이 시작하면서 arr[i]을 더하여 비교해줍니다.

 

이 때, 비교 과정을 두번을 거칩니다.

 

1. arr[0](subarrsum) + arr[i]  //  arr[i]

arr[i]을 더해주는 것이 큰 값인지 아니면 arr[i]자체가 큰지 비교를 해줍니다.

큰 값은 aubarrsum변수에 다시 넣어줍니다.

이렇게 크기를 대조하는 것은 먼저 arr[i]에 대한 변수를 먼저 확인하는것이 생각하기 편합니다.

 

2. 1번에서 Math.max를 통해 비교한 큰값, 즉 arr[i]가 포함이거나 arr[i]인 (aubarrsum) // arr[0](result)을 비교합니다.

 

이렇게 비교 해주어야만, arr[0] + arr[i] , arr[i],  arr[0]을 세 가지의 경우가 비교가 가능합니다.

 

 

subarrsum +arr[i]를 더하는것이 무조건 크다고 생각을 하여 result,  result + arr[i](2번과정)을 바로 비교하면 되지 않을까 생각을 하였지만, 이 문제에서는 연속된 배열로 더해서 큰 값을 찾아야 하기 때문에, 중간에 -1이 있어도 -1을 더해주는것이 더 큰 값이 나오므로 1번과 2번의 비교 과정을 거쳐야 합니다.

 

[4, -1 , 5] 배열을 예시로 사용하면 금방 이해가 됩니다.

 

코드

const LSCS = function (arr) {
  let subArrSum = arr[0];
  let result = arr[0]; // 정답 저장
  
  for (let i = 1; i < arr.length; i++) {
    subArrSum = Math.max(subArrSum + arr[i], arr[i]); // 비교 1
    result = Math.max(result, subArrSum); // 비교 2
  }

  return result;
};