सी++ में मी से कम या उसके बराबर लंबाई की अधिकतम योग सरणी खोजें

समस्या में, हमें अलग-अलग लंबाई के n सरणियाँ दी गई हैं। हमारा काम मी से कम या उसके बराबर लंबाई की अधिकतम योग सरणी खोजना है।

योग को अधिकतम करने के लिए हमें सरणियों से उप-सरणी खोजने की आवश्यकता है और सभी उप-सरणी की लंबाई को m के बराबर बनाने की आवश्यकता है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

n = 3, m = 4
arrOfArr[][] = {
   {5, 2, -1, 4, -3}
   {3, -2, 1, 6}
   {-2, 0, 5}
}

आउटपुट

20

स्पष्टीकरण

SubArrays are {5, 4}, {6}, {5},
length = 2 + 1 + 1 = 4
Sum = 5 + 4 + 6 + 5 = 20

समाधान दृष्टिकोण

गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करके समस्या को हल किया जा सकता है। हम एक DP सरणी बनाएंगे और लंबाई k के संचयी सरणी योगों की गणना करेंगे जो 0 से m तक भिन्न होता है।

DP सरणी में, 2D DP में 0 से m foreach सरणी तक की सभी लंबाई के लिए अधिकतम सरणी योग संग्रहीत करें। फिर अधिकतम योग लौटाएं जो सरणी की अंतिम पंक्ति में होगा।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

उदाहरण

#include <bits/stdc++.h>
using namespace std;
#define N 5
int findMax(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxSumArray(int arr[][N], int M) {
   int DP[N][M];
   int sumArray[M];
   int sum[M];
   memset(DP, -1, sizeof(DP[0][0]) * N * M);
   sumArray[0] = 0;
   DP[0][0] = 0;
   for (int i = 1; i <= 5; i++) {
      int len = arr[i - 1][0];
      for (int j = 1; j <= len; j++) {
         sumArray[j] = arr[i - 1][j];
         sumArray[j] += sumArray[j - 1];
         sum[j] = -100;
      }
      for (int j = 1; j <= len && j <= 6; j++)
         for (int k = 1; k <= len; k++)
            if (j + k - 1 <= len)
               sum[j] = findMax(sum[j], sumArray[j + k - 1] - sumArray[k - 1]);
         for (int j = 0; j <= 6; j++)
            DP[i][j] = DP[i - 1][j];
         for (int j = 1; j <= 6; j++)
            for (int cur = 1; cur <= j && cur <= len; cur++)
               DP[i][j] = findMax(DP[i][j], DP[i - 1][j - cur] + sum[cur]);
   }
   int maxSum = 0;
   for (int i = 0; i <= 6; i++)
      maxSum = findMax(maxSum, DP[5][i]);
      return maxSum;
}
int main() {
   int arr[][N] = { { 3, 2, -1, 6 },
   { 2, 7, -1 },
   { 3, 2, 2, -4 } };
   int m = 4;
   cout<<"Maximum sum array of length less than or equal to "<<m<<" : "<<findMaxSumArray(arr, m);
}

आउटपुट

Maximum sum array of length less than or equal to 4 : 15