Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 최대 K개 배열 요소의 부호를 뒤집어 최대 부분 배열 합 구하기

문제 개요

이 문제에서는 하나의 배열과 정수 k가 주어집니다. 목표는 최대 k개의 배열 요소의 부호를 뒤집어(flip) 얻을 수 있는 최대 부분 배열 합(maximum subarray sum)을 구하는 프로그램을 C++로 작성하는 것입니다.

즉, 배열에서 최대 k개의 요소를 골라 부호를 반대로 바꿨을 때 만들 수 있는 부분 배열(subarray)의 합이 가장 커지도록 하는 것이 핵심입니다.

예시

  • 입력: array = {1, -2, 7, 0}, k = 2
  • 출력: 10
  • 설명: 요소 중 -2 하나만 부호를 뒤집으면 {1, 2, 7, 0}이 되어 합이 10이 되고, 이것이 가능한 최댓값입니다.

해결 접근 방식: 동적 계획법

이 문제는 동적 계획법(Dynamic Programming)과 메모이제이션(memoization)을 활용해 효율적으로 해결할 수 있습니다. 기본 아이디어는 다음과 같습니다.

  1. findSubarraySum(i, flips) 함수는 i번째 인덱스부터 시작하는 부분 배열에서, 지금까지 flips번 부호를 뒤집었다고 가정할 때 얻을 수 있는 최대 합을 반환합니다.
  2. 각 위치에서 두 가지 선택을 고려합니다. 현재 요소를 그대로 사용하는 경우(a[i] + 다음 호출)와, 부호를 뒤집는 경우(-a[i] + 다음 호출, 플립 횟수 1 증가)입니다.
  3. 부분 배열은 어느 시점에서든 끝날 수 있으므로 max(0, ...)를 취해 음수가 되는 구간은 잘라냅니다.
  4. 계산 결과는 maxSumij[i][flips] 배열에 저장해 같은 상태를 반복해서 계산하지 않도록 합니다.
  5. 마지막에는 모든 시작 인덱스에 대해 함수를 호출하고 그중 최댓값을 답으로 반환합니다.

플립 횟수가 k를 초과하면 유효하지 않은 상태이므로 매우 작은 값(-1e9)을 반환해 해당 경로를 배제합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define right 2
#define left 4
int arraySumij[left][right];
int findSubarraySum(int i, int flips, int n, int a[], int k){
    if (flips > k)
        return -1e9;
    if (i == n)
        return 0;
    if (arraySumij[i][flips] != -1)
        return arraySumij[i][flips];
    int maxSum = 0;
    maxSum = max(0, a[i] + findSubarraySum(i + 1, flips, n, a, k));
    maxSum = max(maxSum, -a[i] + findSubarraySum(i + 1, flips + 1, n, a, k));
    arraySumij[i][flips] = maxSum;
    return maxSum;
}
int maxSubarraySumFlip(int a[], int n, int k){
    memset(arraySumij, -1, sizeof(arraySumij));
    int maxSum = -100;
    for (int i = 0; i < n; i++)
        maxSum = max(maxSum, findSubarraySum(i, 0, n, a, k));
    return maxSum;
}
int main() {
    int a[] = {-3, 56, -1, 8};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 2;
    cout<<"Maximum subarray sum by flipping signs of at most "<<k<<" element is "<<maxSubarraySumFlip(a, n, k);
    return 0;
}

실행 결과

Maximum subarray sum by flipping signs of at most 2 element is 66

예제의 입력 배열은 {-3, 56, -1, 8}이고 k = 2입니다. 음수인 -3과 -1의 부호를 뒤집으면 {3, 56, 1, 8}이 되어 전체 합이 66이 되며, 이것이 이 배열에서 얻을 수 있는 최대 부분 배열 합입니다.

복잡도 분석

메모이제이션 덕분에 각 상태(인덱스, 플립 횟수)는 한 번만 계산되므로, 시간 복잡도는 O(n × k)이고 공간 복잡도 역시 O(n × k)입니다. 여기서 n은 배열의 크기, k는 뒤집을 수 있는 최대 요소 개수입니다.

마무리

동적 계획법과 메모이제이션을 활용하면 최대 k개의 요소 부호를 뒤집는 모든 경우를 효율적으로 탐색하면서 최대 부분 배열 합을 구할 수 있습니다. '현재 위치 + 남은 연산 횟수'를 상태로 결합하는 이 패턴은 유사한 유형의 변형 문제에도 널리 활용되므로 잘 익혀두면 유용합니다.