알고리즘.3

seunghyun_kim·2020년 6월 30일
0

알고리즘

목록 보기
3/4

힌트
포문 하나로 원소를 탐색하면서 sum을 업데이트 할 변수 sum 하나랑 , sum이 작아지면 sum이 가장 큰 상태였던 sum을 저장해 둘 또 다른 변수 maxSum을 이용하면 maxSum이 배열 내 연속적인 가장 큰 합이 됩니다.

모범답안1

function maxSubArray(nums: number[]): number {
    let sum = 0 // 현재 최대값
    let maxSum = nums[0]; // 전체 최대값
    if (nums.length === 1) return maxSum;
    nums.forEach((num, index) => {
        if (num > sum + num) { // 현재 숫자가 최대 + 현재보다 더 크면 sum 새로 시작
            sum = num;
        } else {
            sum += num;
        }
        if(sum >= maxSum) { // 현재 최대가 가장 크면 maxSum 업데이트
            maxSum = sum;
        }
        console.log(num, sum, maxSum);
    });
    return maxSum;
};
==> 통과

모범답안

function maxSubArray(A) {
  var prev = 0;
  var max = -Number.MAX_VALUE;

  for (var i = 0; i < A.length; i++) {
    prev = Math.max(prev + A[i], A[i]);
    max = Math.max(max, prev);
  }
  return max;
}

여기서 언급된 Number.MAX_VALUE의 이유와 의미에 감이 오지 않는다.
MAX_VALUE는 자바스크립트 숫자객체의 정적 속성이다. Number.MAX_VALUE 일때만 사용가능? no idea at all

모범답안2

var maxSubArray = function(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개의 댓글