C++でストリートを横断するために必要な最小初期エネルギー

正の数と負の数が格納されている配列があるとします。配列は、通りの一方の端からもう一方の端までのチェックポイントを表しています。正の値と負の値は、チェックポイントでのエネルギーを表しています。正の値はエネルギーを増加させ、負の数はエネルギーを減少させます。エネルギーレベルが0または0未満にならないように、通りを横断するための初期エネルギーレベルを見つける必要があります。

配列A={4、-6、2、3}があるとします。初期エネルギーを0とします。したがって、最初のチェックポイントに到達した後、エネルギーは4になります。次に、2番目のチェックポイントに移動すると、エネルギーは4 +（-6）=-2になります。したがって、エネルギーは0未満です。したがって、3から旅を開始する必要があります。したがって、最初のチェックポイントの後は3 + 4 =7になり、2番目のチェックポイントに移動した後は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