이 문제에서는 N개의 정수와 두 개의 인덱스 값 x와 y로 구성된 배열 arr[]이 제공됩니다. 우리의 임무는 C++에서 접두사와 접두사 뒤에 주어진 요소에서 최대 합 증가 부분 수열을 찾는 프로그램을 만드는 것입니다.
문제 설명
인덱스 x까지 증가하는 시퀀스와 인덱스 y에 있는 요소를 포함하는 시퀀스의 최대 합을 찾습니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6 출력
26
설명
인덱스 3까지 하위 시퀀스를 사용하고 마지막으로 arr[6] =11을 포함합니다.
하위 시퀀스는 {1, 5, 9, 11}입니다. 합계 =1+5+9+11 =26
해결 방법
간단한 접근 방식은 x 인덱스까지 새 배열을 만든 다음 끝에 인덱스 y에 요소를 추가하는 것입니다. 그런 다음 증가하는 모든 부분 수열을 계산한 다음 요소를 포함할 수 없는 모든 것을 버리고 maxSum을 찾습니다.
문제를 해결하기 위한 또 다른 효과적인 접근 방식은 동적 프로그래밍 접근 방식을 사용하는 것입니다. 아이디어는 2차원 배열 DP[][]를 만들고 증가하는 부분 수열의 최대 합을 저장하는 것입니다. DP[x][y]의 값은 요소 arr[y]를 포함하는 인덱스 x까지의 최대 합계를 제공합니다.
예
솔루션의 작동을 설명하는 프로그램,
#include <iostream>
using namespace std;
int DP[100][100];
void preCalcMaxSum(int arr[], int N){
for (int i = 0; i < N; i++) {
if (arr[i] > arr[0])
DP[0][i] = arr[i] + arr[0];
else
DP[0][i] = arr[i];
}
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[j] > arr[i] && j > i) {
if (DP[i - 1][i] + arr[j] > DP[i - 1][j])
DP[i][j] = DP[i - 1][i] + arr[j];
else
DP[i][j] = DP[i - 1][j];
}
else
DP[i][j] = DP[i - 1][j];
}
}
}
int main() {
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
preCalcMaxSum(arr, N);
cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
cout<<DP[x][y];
return 0;
} 출력
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26
효율적인 접근 방식 시퀀스의 가장 큰 요소가 인덱스 y의 요소보다 작은 방식으로 인덱스 x까지 증가하는 부분 시퀀스의 최대 합을 찾는 데 를 사용합니다. 이를 위해 우리는 다시 동적 프로그래밍 접근 방식을 사용할 것입니다.
예
솔루션의 작동을 설명하는 프로그램,
#include <iostream>
using namespace std;
int calcMaxSum(int arr[], int n, int x, int y){
int DP[x] = {0};
int maxSum = -1;
for (int i = 0; i <= x; i++)
DP[i] = arr[i];
for (int i = 0; i <= x; i++) {
if (arr[i] >= arr[y]) {
continue;
}
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j])
DP[i] += arr[j];
maxSum = max(maxSum, DP[i]);
}
}
if (maxSum == -1) {
return arr[y];
}
return maxSum + arr[y];
}
int main(){
int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
int N = sizeof(arr) / sizeof(arr[0]);
int x = 4, y = 6;
cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
cout<<calcMaxSum(arr, N, x, y);
return 0;
} 출력
The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26