C ++では、プレフィックスとプレフィックス後の特定の要素からのサブシーケンスの最大合計が増加する必要があります

この問題では、N個の整数と2つのインデックス値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に要素を追加することです。次に、増加するすべてのサブシーケンスを計算し、要素arr [y]を含めることができないものをすべて破棄して、maxSumを見つけます。

この問題を解決するためのもう1つの効果的なアプローチは、動的計画法のアプローチを使用することです。アイデアは、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