C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++プログラムの配列で距離

この問題では、サイズnと整数kの配列arr[]が与えられます。私たちのタスクは、配列内の距離

問題の説明 −互いにkの距離にある要素を考慮したサブシーケンスの最大合計を見つける必要があります。

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

入力

arr[] = {6, 2, 5, 1, 9, 11, 4} k = 2

出力

16

説明

All possible sub−sequences of elements that differ by k or more.
{6, 1, 4}, sum = 11
{2, 9}, sum = 11
{5, 11}, sum = 16
{1, 4}, sum = 5
...
maxSum = 16

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

この問題の解決策は、動的計画法を使用することです。解決策として、配列の現在の要素まで可能な最大の合計を見つけます。そして、それをDP [i]に格納します。これにより、可能な最大の合計が見つかります。i番目のインデックスの場合、現在のインデックス値を追加するとサブシーケンスの合計が増えるかどうかを確認する必要があります。

if( DP[i − (k+1)] + arr[i] > DP[i − 1] )
−> DP[i] = DP[i − (k+1)] + arr[i]
otherwise DP[i] = DP[i−1]

動的配列の最大要素は、最大サブシーケンス合計を示します。

アルゴリズム

初期化 − 

maxSumSubSeq = −1, maxSumDP[n]

ステップ1 − 

Initialize maxSumDP[0] = arr[0]

ステップ2 − 

Loop for i −> 1 to n.

ステップ2.1 − 

if i < k −> maxSumDP[i] = maximum of arr[i] or
maxSumDP[i− 1].

ステップ2.2 − 

else, maxSumDP[i] = maximum of arr[i] or maxSumDP[i − (k + 1)] + arr[i].

ステップ3 − 

Find the maximum value of all elements from maxSumDP and store
it to maxSumSubSeq.

ステップ4 − 

Return maxSumSubSeq

例

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

#include <iostream>
using namespace std;
int retMaxVal(int a, int b){
   if(a > b)
   return a;
   return b;
}
int calcMaxSumSubSeq(int arr[], int k, int n) {
   int maxSumDP[n];
   int maxSum = −1;
   maxSumDP[0] = arr[0];
   for (int i = 1; i < n; i++){
      if(i < k ){
         maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − 1]);
      }
      else
      maxSumDP[i] = retMaxVal(arr[i], maxSumDP[i − (k +
      1)] + arr[i]);
   }
   for(int i = 0; i < n; i++)
   maxSum = retMaxVal(maxSumDP[i], maxSum);
   return maxSum;
}
int main() {
   int arr[] = {6, 2, 5, 1, 9, 11, 4};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 2;
   cout<<"The maximum sum possible for a sub−sequence such
   that no two elements appear at a distance < "<<k<<" in the array is "<<calcMaxSumSubSeq(arr, k, n);
   return 0;
}

出力

The maximum sum possible for a sub−sequence such that no two
elements appear at a distance < 2 in the array is 16

  1. C++で2つの要素が隣接しないような循環配列の最大合計

    この問題では、循環配列cirArr[]が与えられます。私たちのタスクは、C++で2つの要素が隣接しないように循環配列の最大合計を見つけるプログラムを作成することです。 問題の説明 循環配列の場合、隣接する要素を取得できないように、配列の要素の最大合計を見つける必要があります。つまり、代替要素を取得する必要があります。 循環アレイ は、配列の最後の要素が最初の要素に接続されている特殊なタイプの配列です。 問題を理解するために例を見てみましょう 入力 cirArr[] = {4, 1, 5, 3, 2} 出力 9 説明 最大合計循環サブシーケンスは[4、5、2]です。合計=9 ソリ

  2. 配列要素の乗算のためのC++プログラム

    整数要素の配列で与えられ、タスクは配列の要素を乗算して表示することです。 例 Input-: arr[]={1,2,3,4,5,6,7} Output-: 1 x 2 x 3 x 4 x 5 x 6 x 7 = 5040 Input-: arr[]={3, 4,6, 2, 7, 8, 4} Output-: 3 x 4 x 6 x 2 x 7 x 8 x 4 = 32256 以下のプログラムで使用されるアプローチは次のとおりです − 一時変数を初期化して、最終結果を1で格納します ループを0からnまで開始します。nは配列のサイズです 最終結果を得るには、tempの値にarr[i]を掛け続