C में खरीदी जा सकने वाली अधिकतम कैंडीज की संख्या

समस्या विवरण

हमें एक कैंडीज सरणी candies[] दी गई है जिसकी लंबाई size में संग्रहीत है। प्रत्येक तत्व candies[i] प्रकार i की कैंडीज की संख्या दर्शाता है। लक्ष्य किसी भी राशि के लिए अधिकतम कैंडीज खरीदना है। शर्तें निम्नलिखित हैं:

यदि आप प्रकार i की X[i] कैंडीज खरीदते हैं (0 <= X[i] <= candies[i]), तो सभी j (1 <= j <= i) के लिए निम्न में से कम से कम एक शर्त सत्य होनी चाहिए:

X(j) < X(i) (प्रकार j की खरीदी गई कैंडीज प्रकार i से कम)
X(j) = 0, प्रकार j की कोई कैंडी नहीं खरीदी गई

उदाहरण 1

इनपुट: Arr[] = {1, 3, 5, 2, 6, 7}

आउटपुट: अधिकतम कैंडीज जो खरीदी जा सकती हैं: 16

व्याख्या: खरीदी गई कैंडीज प्रकार i: {0, 3, 5, 2, 6, 0}

उदाहरण 2

इनपुट: Arr[] = {5, 7, 7, 3, 4}

आउटपुट: अधिकतम कैंडीज जो खरीदी जा सकती हैं: 10

व्याख्या: खरीदी गई कैंडीज प्रकार i: {0, 0, 7, 3, 0}

दृष्टिकोण

पूर्णांक सरणी candies[] प्रकार i की कैंडीज की संख्या संग्रहीत करती है।
चर size सरणी की लंबाई संग्रहीत करता है।
फ़ंक्शन maxCandies(int arr[], int n) खरीदी जा सकने वाली कुल कैंडीज लौटाता है।
मान लें हमने अंतिम प्रकार की कैंडीज खरीदी: bought = arr[n-1]
दूसरे अंतिम तत्व से शुरू करें: for(i = n-2; i >= 0; i--)
चर x वर्तमान प्रकार की खरीदी जा सकने वाली कैंडीज संग्रहीत करता है: x = min(arr[i], bought-1)
यदि x शून्येतर है तो कुल में जोड़ें।
यदि कुल पिछले bought मान से अधिक है तो bought = x।
परिणाम लौटाएं।

C प्रोग्राम उदाहरण

#include <stdio.h>

int maxCandies(int arr[], int n) {
    int bought = arr[n - 1];
    int total = bought;
    // दूसरे अंतिम से शुरू
    for (int i = n - 2; i >= 0; i--) {
        // वर्तमान प्रकार की खरीदी जा सकने वाली कैंडीज
        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