각각 크기가 N인 지정된 두 개의 배열에 대해 작업은 배열 1에서 X 요소를 선택하고 배열 2에서 Y 요소를 선택하여 최대 합을 찾는 것입니다.
이제 예제를 사용하여 무엇을 해야 하는지 이해합시다 -
입력
arr1 = {1,2,3,4,5} ; X=2
arr2 = {1,3,5,2,7}; Y=3 출력
Maximum sum here is : 24
설명 - 우리는 arr1에서 2개의 숫자를 선택하고 arr2에서 3을 선택합니다. arr1의 가장 큰 2는 4,5이고 arr2의 가장 큰 3은 3,5,7입니다. 이 5가지 요소의 총합은 요구 사항에 따라 최대인 24입니다.
입력
arr1 = {10,13,16,14}; X=1
arr2 = {4,1,2,1}; Y=2 출력
Maximum sum here is : 22
설명 − arr1에서 1개의 숫자를 선택하고 arr2에서 2개를 선택합니다. arr1의 가장 큰 것은 16이고 arr2의 가장 큰 2는 4,2입니다. 이 5가지 요소의 총합은 요구 사항에 따라 최대인 22입니다.
아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.
-
입력 배열 arr1[] 및 arr2[]와 X 및 Y 값을 가져옵니다.
-
두 배열을 오름차순으로 정렬합니다.
-
arr1에서 마지막 X 요소를 가져오고 Arr2에서 Y 요소가 가장 높으므로 가져옵니다.
-
마지막으로 3단계에서 선택한 요소의 합을 최대값으로 반환합니다.
-
참고:sort(arr[],int)는 정렬된 배열을 반환한다고 가정합니다.
예
#include <iostream>
using namespace std;
int max_sum(int arr1[],int arr2[], int length,int X,int Y){
//for sorting the array
sort(arr1,length);
sort(arr2,length);
int sum=0;
int i;
//adding last X elements from arr1 and last Y elements from arr2
for(i=0;i<X;i++){
sum+=arr1[length-i-1];
}
for(i=0;i<Y;i++){
sum+=arr2[length-i-1];
}
return(sum);
}
// Driver program
int main(){
int arr1[]={1,1,1,3,7};
int arr2[]={1,1,2,3,5};
int x=3,y=2;
printf( "Maximized sum of X+Y elements by picking X and Y elements from 1st and 2nd array is %d",max_sum(arr1,arr2,5,x,y));
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다 -
Maximized sum of X+Y elements by picking X and Y elements from 1st and 2nd array is 19