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

C++で少なくともk個の離れた要素を持つ最大合計サブシーケンス

このチュートリアルでは、少なくともk個の離れた要素を持つ最大の合計サブシーケンスを見つけるプログラムについて説明します。

このために、整数と値Kを含む配列が提供されます。私たちのタスクは、すべての要素が少なくともK要素離れているような最大の合計を持つサブシーケンスを見つけることです。

例

#include <bits/stdc++.h>
using namespace std;
//finding maximum sum subsequence
int maxSum(int arr[], int N, int k) {
   int MS[N];
   MS[N - 1] = arr[N - 1];
   for (int i = N - 2; i >= 0; i--) {
      if (i + k + 1 >= N)
         MS[i] = max(arr[i], MS[i + 1]);
      else
         MS[i] = max(arr[i] + MS[i + k + 1], MS[i + 1]);
   }
   return MS[0];
}
int main() {
   int N = 10, k = 2;
   int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
   cout << maxSum(arr, N, k);
   return 0;
}

出力

230

  1. C++で指定された合計の最大サイズサブセット

    問題の説明 N個の要素と合計の配列が与えられます。合計が与えられた合計に等しい最大サイズのサブセットのサイズを見つける必要があります 例 入力配列がarr={2、3、5、10}でsum =20の場合、出力は-として4になります。 2 + 3 + 5 + 10=20これは与えられた合計に等しい アルゴリズム 動的計画法を使用してこの問題を解決できます。 最大サブセットをカウントするには、別のDP配列（「カウント配列」と呼ばれます）を使用します。ここで、count[i][j]は最大です。 count[i][j-1]。ここでは、現在の要素は考慮されていません。 scount [i-

  2. C ++を使用して、マトリックス内の合計が最大の列を検索します。

    サイズがMxNの行列があるとします。合計が最大の列を見つける必要があります。このプログラムでは、トリッキーなアプローチには従わず、配列を列ごとにトラバースし、各列の合計を取得します。合計が最大の場合は、合計と列インデックスを出力します。 例 #include<iostream> #define M 5 #define N 5 using namespace std; int colSum(int colIndex, int mat[M][N]){    int sum = 0;    for(int i = 0; i<M; i++){