Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में लंबाई m से कम या बराबर अधिकतम योग सरणी ज्ञात करें


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

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

आइए एक उदाहरण से समझते हैं:

इनपुट

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

आउटपुट

20

व्याख्या

उप-सरणियाँ हैं {5, 4}, {6}, {5}, लंबाई = 2 + 1 + 1 = 4 योग = 5 + 4 + 6 + 5 = 20

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

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

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

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम:

उदाहरण

#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

  1. बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में

    मान लीजिए हमारे पास एक बाइनरी ट्री है। कार्य वर्टिकल ऑर्डर ट्रैवर्सल में सभी नोड्स के योग के अधिकतम को प्रिंट करना है। तो यदि ट्री नीचे जैसा है - वर्टिकल ऑर्डर ट्रैवर्सल इस तरह है - 4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9 यहां अधिकतम 12 है। दृष्टिकोण सरल है। हम वर्टिकल ऑर्डर ट्रैवर्सल करेंगे, फिर योग खोज

  1. - C++ में n से कम या बराबर सभी फैक्टोरियल संख्याएं खोजें

    यहां हम देखेंगे कि n से कम या बराबर सभी फैक्टोरियल संख्याओं को कैसे प्रिंट किया जाए। एक संख्या N को फैक्टोरियल संख्या कहा जाता है यदि यह किसी धनात्मक संख्या का फैक्टोरियल है। इसलिए कुछ फैक्टोरियल संख्याएं हैं: 1, 2, 6, 24, 120। फैक्टोरियल संख्याओं को प्रिंट करने के लिए, हमें सीधे फैक्टोरियल खोजने क

  1. - C++ में सरणी में अधिकतम GCD वाली जोड़ी ढूंढना

    मान लीजिए हमारे पास धनात्मक पूर्णांकों की एक सरणी है। हमारा कार्य सरणी से पूर्णांकों की जोड़ी ढूंढना है, जहां GCD मान अधिकतम है। मान लीजिए A = {1, 2, 3, 4, 5}, तो आउटपुट 2 है। जोड़ी (2, 4) का GCD 2 है, अन्य GCD मान 2 से कम हैं।इस समस्या को हल करने के लिए, हम एक काउंट सरणी बनाए रखेंगे जो प्रत्येक तत्