C++-এ রাস্তা পার করার জন্য ন্যূনতম প্রাথমিক আনার্জি বের করা

মনে করুন একটি অ্যারে আছে যেখানে পজিটিভ এবং নেগেটিভ সংখ্যা স্টোর করা আছে। অ্যারেটি চেকপয়েন্ট গুলো রিপ্রেজেন্ট করে রাস্তার এক ছোর থেকে অন্য ছোর পর্যন্ত। পজিটিভ এবং নেগেটিভ মান গুলো চেকপয়েন্ট গুলোর আনার্জি রিপ্রেজেন্ট করে। পজিটিভ মান আনার্জি বাড়ায়, এবং নেগেটিভ সংখ্যা আনার্জি কমায়। আমাদের প্রাথমিক আনার্জি লেভেল বের করতে হবে যাতে রাস্তা পার করা যায়, যেন আনার্জি লেভেল কখনো ০ বা ০-এর চেয়ে কম হয় না।

মনে করুন у нас একটি অ্যারে A = {4, -6, 2, 3}। প্রাথমিক আনার্জি ০ ধরি। প্রথম চেকপয়েন্টে পৌঁছালে আনার্জি ৪। এখন, দ্বিতীয় চেকপয়েন্টে যেতে আনার্জি হবে ৪ + (-6) = -২। তাই আনার্জি ০-এর চেয়ে কম। সুতরাং আমাদের ৩ দিয়ে যাত্রা শুরু করতে হবে। তাহলে প্রথম চেকপয়েন্টে হবে ৩ + ৪ = ৭, এবং দ্বিতীয় চেকপয়েন্টে যেতে হবে ৭ + (-6) = ১।

অ্যালগরিদম

minInitEnergy(arr, n): 
শুরু 
    initEnergy := 0
    currEnergy := 0
    flag := false
    i = 0 থেকে n পর্যন্ত, করো
        currEnergy := currEnergy + arr[i]
        যদি currEnergy <= 0, তবে
            initEnergy := initEnergy + |currEnergy| + 1
            currEnergy := 1
            flag := true
        শেষ যদি
    শেষ
    যদি flag false হয়, ১ রিটার্ন করো, অন্যথায় initEnergy রিটার্ন করো
শেষ

উদাহরণ (C++ কোড)

#include <iostream>
#include <cmath>
using namespace std;

int minInitEnergy(int arr[], int n) {
    int initEnergy = 0;
    int currEnergy = 0;
    bool flag = false;
    for (int i = 0; i < n; i++) {
        currEnergy = currEnergy + arr[i];
        if (currEnergy <= 0) {
            initEnergy = initEnergy + abs(currEnergy) + 1;
            currEnergy = 1;
            flag = true;
        }
    }
    if (flag == false)
        return 1;
    else
        return initEnergy;
}

int main() {
    int A[] = {4, -6, 2, 3};
    int n = sizeof(A)/sizeof(A[0]);
    cout << "Minimum Energy: " << minInitEnergy(A, n);
}

আউটপুট

Minimum Energy: 3