1.5.13 최대 경로 합
문제 1-13 오름차순인 두 배열이 주어졌을 때 한 배열에서 연속된 원소를 몇 개 고르고 다른 배열에서 연속된 원소를 골라 이 원소들을 합했을 때 나올 수 있는 최댓값을 구합니다. 원소를 고르는 배열을 변경하는 것은 두 배열이 같은 값을 가지는 지점에서만 가능합니다.9
예시
arr1 = [12, 13, 18, 20, 22, 26, 70]
arr2 = [11, 15, 18, 19, 20, 26, 30, 31]
최대 합을 구성하는 원소: 11, 15, 18, 19, 20, 22, 26, 70
최대 합: 201
해결책 1-13
int maxPathSum(int arr1[], int size1, int arr2[], int size2) { int i = 0, j = 0, result = 0, sum1 = 0, sum2 = 0; while (i < size1 && j < size2) { if (arr1[i] < arr2[j]) { sum1 += arr1[i]; i += 1; } else if (arr1[i] > arr2[j]) { sum2 += arr2[j]; j += 1; } else { result += max(sum1, sum2); result = result + arr1[i]; sum1 = 0; sum2 = 0; i += 1; j += 1; } } while (i < size1) { sum1 += arr1[i]; i += 1; } while (j < size2) { sum2 += arr2[j]; j += 1; } result += max(sum1, sum2); return result; } /* 테스트 코드 */ int main() { int arr1[] = { 12, 13, 18, 20, 22, 26, 70 }; int arr2[] = { 11, 15, 18, 19, 20, 26, 30, 31 }; printf("최대 경로 합: %d", maxPathSum(arr1, sizeof(arr1) / sizeof(int), arr2, sizeof(arr2) / sizeof(int))); }
분석 시간 복잡도는 O(n)이며, 공간 복잡도는 O(n)입니다.
9 역주 예를 들어 이 예제에서는 18, 20, 26이 두 배열에서 값이 같은 지점이고, 이 지점에서 arr2 → arr2 → arr1 → arr1 순으로 선택해 최대 합을 구하고 있습니다.