हमें कैंडीज की एक सरणी दी गई है [] लंबाई की 'आकार' में संग्रहीत। प्रत्येक तत्व कैंडीज [i] में i प्रकार की कैंडीज के लिए एक संख्या होती है। लक्ष्य किसी भी राशि के लिए अधिक से अधिक कैंडी खरीदना है। शर्तें इस प्रकार हैं -
यदि आप I (0<=X[i] <=कैंडीज[i] ) प्रकार का X[i] खरीदते हैं, तो सभी j ( 1<=j<=i ) के लिए कम से कम निम्नलिखित में से एक शर्त सही होनी चाहिए -
-
X(j)
-
X(j)=0, j प्रकार की कोई कैंडी नहीं खरीदी गई
आइए उदाहरणों से समझते हैं।
इनपुट - एआर [] ={ 1,3,5,2,6,7}।
आउटपुट - अधिकतम कैंडीज जो खरीदी जा सकती हैं - 16
स्पष्टीकरण - i { 0,3,5,2,6,0 }
. प्रकार की खरीदी गई कैंडीजइनपुट - अरे [] ={ 5,7,7,3,4}।
आउटपुट - अधिकतम कैंडीज जो खरीदी जा सकती हैं - 10
स्पष्टीकरण - i { 0,0,7,3,0 }
. प्रकार की खरीदी गई कैंडीजनीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक सरणी कैंडीज [] का उपयोग प्रकार की कैंडी की संख्या को संग्रहीत करने के लिए किया जाता है।
-
चर 'आकार' सरणी कैंडीज की लंबाई संग्रहीत करता है।
-
फंक्शन maxCandies(int arr[], int n) का उपयोग उन कैंडीज की कुल संख्या को वापस करने के लिए किया जाता है जिन्हें खरीदा जा सकता है।
-
पहले मान लीजिए हमने आखिरी प्रकार की कैंडी खरीदी। खरीदा=गिरफ्तारी[n-1]
-
दूसरे अंतिम तत्व से शुरू, for(i=n-2;i>=0;i--)
-
चर x वर्तमान प्रकार की कैंडीज की मात्रा को संग्रहीत करता है जिसे खरीदा जा सकता है। x=arr[i] या ख़रीदा गया-1 जो भी कम हो।
-
अगर x गैर-शून्य है तो इसे कुल में जोड़ें।
-
यदि कुल पिछले खरीदे गए मूल्य से अधिक है तो खरीदा =x।
-
ख़रीदा गया परिणाम लौटाएँ।
उदाहरण
#include <stdio.h>
int maxCandies(int arr[], int n){
int bought = arr[n - 1];
int total = bought;
// Starting from second last
for (int i = n - 2; i >= 0; i--) {
// Amount of candies of the current
// type that can be bought
int x = arr[i]<bought-1?arr[i]:bought-1;
if (x >= 0) {
total += x;
bought = x;
}
}
return total;
}
int main(){
int candies[] = { 1,2,4,3,7 };
int size = 5;
printf("Total Candies that can be bought: %d", maxCandies(candies, size));
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Total Candies that can be bought: 13