부분 배열의 최대합

[hsskey]

부분 배열의 최대합

사이즈가 k인 부분배열(subarray)의 최대 합을 구하시오

📝 제약조건

• 제약조건 작성

💡 예시

• Input: arr = [5, 7, -1, 14, 3, 12, 1, 4], k = 3
  • Output: 29

문제 해결 과정

Step 1: 문제 이해하기

• 제약조건, input, output을 확인하여 문제를 정확히 파악합니다.

Step 2: 접근 방법

• 직관적으로 생각하기
  • 완전탐색(인덱스를 기준으로 k만큼의 숫자를 매회 더해주면서 계산)

Step 3: 코드 설계 (수도코드)

maxSum = 0
loop i // i의 범위를 k사이즈를 기준으로 설정
    subArraySum = 0
    loop j
        subArray += arr[j] // k의 사이즈만큼 저장
    maxSum = Math.max(subArraySum, maxSum)
return maxSum

Step 4: 코드 구현 (Brute Force)

function maxSumOfSubArray(arr, k) {
    let maxSum = 0
    for(let i = 0; i < arr.length - k + 1; i ++) {
        let subArraySum = 0
        for(let j = i; j < i + k; j++) {
            subArraySum += arr[j]         }
        maxSum = Math.max(subArraySum, maxSum)
    }
    return maxSum
}

console.log(maxSumOfSubArray([5, 7, -1, 14, 3, 12, 1, 4], 3))

[hsskey]

Step 2: 접근 방법

• 자료구조와 알고리즘 활용
  • 슬라이딩윈도우 활용

Step 3: 코드 설계

loop i // i는 끝까지 이동
    windowSum += arr[i]
    if(인덱스 기준으로 윈도우 범위까지내에서) 
        maxSum 업데이트
        windowSum -= 이전값 빼기
return maxSum

Step 4: 코드 구현

function maxSumOfSubArray(arr, k) {
    let windowSum = 0 // 부분합 저장
    let maxSum = -Infinity // 0 대신 사용하는 이유는 배열중 음수 대비

    for(let i = 0; i < arr.length -1; i++) {
        windowSum += arr[i]
        // 인덱스를 기준으로 윈도우의 범위를 업데이트
        if(i >= k - 1) {
            maxSum = Math.max(windowSum, maxSum)
            windowSum -= arr[i - (k -1)]
        }
    }
    return maxSum
}