7.24일 codewars

samuel Jo·2023년 7월 24일
0

codewars

목록 보기
41/47

1. 주어진 배열에서 최대 부분합을 구하는 문제.

function maxSequence(arr) {
  let currentSum = 0; // 현재 인덱스에서 끝나는 연속 부분 배열의 합
  let maxSum = 0; // 현재까지의 연속 부분 배열 중 최대 합

  for (let i = 0; i < arr.length; i++) {
    // 배열의 각 요소를 순회하며 최대 부분합을 갱신하는 반복문 시작
    currentSum = Math.max(0, currentSum + arr[i]);
    // 현재 인덱스에서 끝나는 연속 부분 배열의 합은 arr[i]를 더한 값과 0 중에서 더 큰 값을 선택.
    // 만약 currentSum + arr[i]가 0보다 작다면, 새로운 부분 배열을 시작하는 것이 이득이기 때문에 0으로 초기화.
    maxSum = Math.max(maxSum, currentSum);
    // 현재까지의 연속 부분 배열 중 최대 합과 현재 인덱스에서 끝나는 연속 부분 배열의 합 중에서 더 큰 값을 선택하여 maxSum에 저장.
  }

  return maxSum;
  // 최종적으로 전체 배열을 순회하며 구한 최대 부분합을 반환.
}

문제를 풀고나서 보니까 카데인 알고리즘과 연관 되어있는걸 알았다.

카데인알고리즘을 꽤나 잘 설명한 영상같아 첨부함

한국어설명(주니온TV 아무거나연구소)

나에겐 좀 어려웠던 문제

profile
step by step

0개의 댓글