C ++中过马路所需的最小初始能量

假设我们有一个存储正负数的数组。该数组代表从街道的一端到另一端的检查点。正值和负值表示检查点的能量。正值可以增加能量，负数可以减少能量。我们必须找到过马路的初始能级，以使能级永远不会变为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