C++での最大合計減少サブシーケンス

この問題では、N個の整数の配列arr[]が与えられます。私たちのタスクは、C++で最大合計減少サブシーケンスを見つけることです。

問題の説明

サブシーケンスが厳密に減少するように、配列から要素の最大合計を見つけます。

問題を理解するために例を見てみましょう

入力

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

出力

17

説明

最大合計でサブシーケンスを減らすと、{10、5、2} =10 + 5 + 2 =17

ソリューションアプローチ

ここでは、動的計画法のアプローチを使用して解決策を見つけます。ここでは、インデックスiまでmaxSumを格納するmaxSum[]配列を作成します。次の式を使用して配列値を検索します

maxSum [i] =arr [i] + max（maxSum [0…（* i-1）]）

最大合計は、配列maxSum[]の最大要素によって与えられます。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int findMaxSumDecSubSeq(int arr[], int N){
   int maximumSum = 0;
   int maxSum[N];
   for (int i = 0; i < N; i++)
      maxSum[i] = arr[i];
   for (int i = 1; i < N; i++)
      for (int j = 0; j < i; j++)
         if (arr[i] < arr[j] && maxSum[i] < maxSum[j] + arr[i])
         maxSum[i] = maxSum[j] + arr[i];
   for (int i = 0; i < N; i++)
         if (maximumSum < maxSum[i])
            maximumSum = maxSum[i];
   return maximumSum;
}
int main(){
   int arr[] = { 5, 4, 100, 3, 2, 101, 1 };
   int N= sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum sum of decreasing subsequence is "<<findMaxSumDecSubSeq(arr, N);
   return 0;
}

出力

The maximum sum of decreasing subsequence is 106