[Algorithm] 연속되는 가장 큰 값 구하기

김진영·2022년 9월 15일
0

Algorithm

목록 보기
6/15
post-thumbnail

📋 중복되지 않는 가장 긴 문자열

숫자로 이루어진 리스트 nums를 인자로 주면, 그 안에서 어떤 연속적인 요소를 더했을 때 가장 큰 값이 나오나요? 가장 큰 값을 찾아 return해주세요.

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
설명: [4,-1,2,1] 를 더하면 6이 가장 크기 때문

사실 전혀 어려울 것 없는 문제지만 내가 푼 풀이보다 훨씬 뛰어난 모범 답안이 있어서 이렇게 블로그에 정리하게 되었다.


📌 1. 내가 작성한 코드

const maxSubArray = nums => {
  const arr = [];
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j]
      arr.push(sum)
    }
  }
  return Math.max(...arr)
};

중첩루프를 통해 풀었다. 간단한 풀이방식이다.


📌 2. 모범 답안

const maxSubArray = nums => {
    for (let i = 1; i < nums.length; i++){
        nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
    }
    return Math.max(...nums);
};

이렇게 중첩루프를 사용하지 않고도 풀이할 수 있는 방법이 있었다.

현재 인덱스를 현재 인덱스 값과 현재 인덱스 값 + 이전 인덱스 값 중 더 큰것으로 대체해 그 중 가장 큰 값을 반환하는 방법이다.

0개의 댓글