मान लीजिए हमारे पास एक ऐरे है जहां पॉजिटिव और नेगेटिव नंबर स्टोर हैं। ऐरे सड़क के एक छोर से दूसरे छोर तक के चेकपॉइंट्स को दर्शाता है। पॉजिटिव और नेगेटिव मान चेकपॉइंट्स पर ऊर्जा को दर्शाते हैं। पॉजिटिव मान ऊर्जा बढ़ाते हैं, और नेगेटिव नंबर ऊर्जा घटाते हैं। हमें प्रारंभिक ऊर्जा स्तर ढूंढना है जिससे सड़क पार की जा सके, ताकि ऊर्जा स्तर कभी 0 या 0 से कम न हो।
मान लीजिए हमारे पास ऐरे A = {4, -6, 2, 3} है। प्रारंभिक ऊर्जा 0 मान लें। तो पहले चेकपॉइंट पर पहुंचने के बाद ऊर्जा 4 होगी। अब दूसरे चेकपॉइंट पर जाने के लिए, ऊर्जा 4 + (-6) = -2 होगी। तो ऊर्जा 0 से कम है। इसलिए हमें यात्रा 3 से शुरू करनी होगी। तो पहले के बाद यह 3 + 4 = 7 होगी, और दूसरे चेकपॉइंट पर जाने के बाद यह 7 + (-6) = 1 होगी।
एल्गोरिदम
minInitEnergy(arr, n): begin initEnergy := 0 currEnergy := 0 flag := false i को 0 से n तक की रेंज में, करें currEnergy := currEnergy + arr[i] यदि currEnergy <= 0, तो initEnergy := initEnergy + currEnergy का निरपेक्ष मान + 1 currEnergy := 1 flag := true end if done यदि flag false है, तो 1 रिटर्न करें, अन्यथा initEnergy रिटर्न करें end
उदाहरण
#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