मान लीजिए कि हमारे पास एक सरणी है जहां सकारात्मक और नकारात्मक संख्याएं संग्रहीत हैं। सरणी सड़कों के एक छोर से दूसरे छोर तक चौकी का प्रतिनिधित्व कर रही है। सकारात्मक और नकारात्मक मान चौकियों पर ऊर्जा का प्रतिनिधित्व कर रहे हैं। सकारात्मक मान ऊर्जा को बढ़ा सकते हैं, और ऋणात्मक संख्या ऊर्जा को कम करती है। हमें सड़क पार करने के लिए प्रारंभिक ऊर्जा स्तर का पता लगाना होगा, ताकि ऊर्जा का स्तर कभी भी 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 for i in range 0 to n, do currEnergy := currEnergy + arr[i] if currEnergy <= 0, then initEnergy := initEnergy + absolute value of currEnergy + 1 currEnergy := 1 flag := true end if done if flag is false, return 1, otherwise return 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