C++ में वितरित टेडी की कुल संख्या न्यूनतम करें

समस्या विवरण

N छात्रों के अंक दिए गए हैं। प्रत्येक को कम से कम 1 टेडी मिले। यदि दो छात्र साथ बैठे हैं तो अधिक अंक वाले को अधिक टेडी मिले। समान अंक वालों को अलग-अलग टेडी मिल सकते हैं। कुल टेडी न्यूनतम करें।

उदाहरण: अंक = {2, 3, 3} → टेडी = {1, 2, 1} → कुल = 4

एल्गोरिदम (डायनामिक प्रोग्रामिंग)

1. सभी को 1 टेडी से शुरू करें
2. बाएं से दाएं: यदि वर्तमान के अंक पिछले से अधिक हैं, तो पिछले + 1 टेडी दें
3. दाएं से बाएं: यदि वर्तमान के अंक अगले से अधिक हैं और टेडी कम/बराबर हैं, तो अगले + 1 टेडी दें

उदाहरण कोड

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int teddieDistribution(int* marks, int n) {
    int table[n];
    fill(table, table + n, 1);
    
    for (int i = 0; i < n - 1; ++i) {
        if (marks[i + 1] > marks[i]) {
            table[i + 1] = table[i] + 1;
        } else if (marks[i] > marks[i + 1]) {
            int temp = i;
            while (true) {
                if (temp >= 0 && marks[temp] > marks[temp + 1]) {
                    if (table[temp] > table[temp + 1]) {
                        --temp; continue;
                    } else {
                        table[temp] = table[temp + 1] + 1;
                        --temp;
                    }
                } else break;
            }
        }
    }
    
    int totalTeddies = 0;
    for (int i = 0; i < n; ++i) totalTeddies += table[i];
    return totalTeddies;
}

int main() {
    int marks[] = {2, 6, 5, 2, 3, 7};
    cout << "Total teddies to be distributed: " << teddieDistribution(marks, SIZE(marks)) << "\n";
    return 0;
}

आउटपुट

Total teddies to be distributed: 12