C++ 프로그램에서 DP를 사용한 최대 합 증가 부분 수열

이 문제에서는 크기가 n인 배열 arr[]이 제공됩니다. 우리의 임무는 C++에서 DP를 사용하여 최대 합 증가 부분 수열을 찾는 프로그램을 만드는 것입니다.

문제 설명 − 최대 합 증가 부분 수열을 찾기 위해 다음 요소가 현재 요소보다 큰 부분 수열을 생성합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

arr[] = {4, 2, 3, 6, 5, 9}

출력

20

설명

Increasing subsequence with maximum sum:
{2, 3, 6, 9} = 2 + 3 + 6 + 9 = 20

솔루션 접근 방식

동적 프로그램 접근 방식을 사용하여 문제를 해결합니다. 현재 요소까지 최대 합계를 저장하는 배열을 만듭니다. 그런 다음 배열에서 maxSum을 반환합니다.

예시

우리 솔루션의 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
int retMaxVal(int x, int y){
   if(x > y)
   return x;
   return y;
}
int calcMaxSubSeqSum(int arr[], int n) {
   int maxSum = 0;
   int sumDP[n];
   for (int i = 0; i < n; i++ )
   sumDP[i] = arr[i];
   for (int i = 1; i < n; i++ )
   for (int j = 0; j < i; j++ )
   if ( (sumDP[i] < (sumDP[j] + arr[i])) && ( arr[i] >
   arr[j] ) )
   sumDP[i] = sumDP[j] + arr[i];
   for (int i = 0; i < n; i++ )
   maxSum = retMaxVal(sumDP[i], maxSum);
   return maxSum;
}
int main() {
   int arr[] = {4, 2, 3, 6, 5, 9};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum Sum Increasing Subsequence using DP is
   "<<calcMaxSubSeqSum(arr, n);
   return 0;
}

출력

Sum of maximum sum increasing subsequence is 20