算法设计（过马路所需的最低初始能量） _数组

本文概述

建议：在继续解决方案之前, 请先在"实践"上解决它。
C / C ++
Java
python
C#
的PHP

给定一个包含正数和负数的数组。该数组表示从街道的一端到另一端的检查点。正值和负值表示该检查点的能量。正数增加能量, 负数减少。找到过马路所需的最小初始能量, 以使能量水平永远不会变为0或小于0。
注意：即使我们成功过马路而在任何检查点都没有将能量损失到小于等于0, 所需的最小初始能量的值为1。初始检查点需要1。
例子：

Input : arr[] = {4, -10, 4, 4, 4}Output: 7Suppose initially we have energy = 0, now at 1stcheckpoint, we get 4. At 2nd checkpoint, energy getsreduced by -10 so we have 4 + (-10) = -6 but at any checkpoint value of energy can not less than equals to 0. So initial energy must be at least 7 becausehaving 7 as initial energy value at 1st checkpointour energy will be = 7+4 = 11 and then we can cross 2nd checkpoint successfully. Now after 2nd checkpoint, all checkpoint have positive value so we can cross street successfully with 7 initial energy.Input : arr[] = {3, 5, 2, 6, 1}Output: 1We need at least 1 initial energy to reach firstcheckpointInput : arr[] = {-1, -5, -9}Output: 16

推荐：请在"实践首先, 在继续解决方案之前。我们取初始最小能量0即initMinEnergy = 0, 任何检查点的能量为currEnergy =0。现在线性遍历每个检查点, 并在第i个检查点添加能量级别, 即； currEnergy = currEnergy + arr [i]。如果currEnergy变为非正数, 那么我们至少需要额外的" abs(currEnergy)+1"初始能量才能跨越这一点。因此, 我们更新initMinEnergy =(initMinEnergy + abs(currEnergy)+ 1)。我们还更新了currEnergy = 1, 因为我们现在拥有下一点所需的额外最小初始能量。
以下是上述想法的实现。
C / C ++

// C++ program to find minimum initial energy to // reach end #include< bits/stdc++.h> using namespace std; // Function to calculate minimum initial energy // arr[] stores energy at each checkpoints on street int minInitialEnergy( int arr[], int n) { // initMinEnergy is variable to store minimum initial // energy required. int initMinEnergy = 0; // currEnergy is variable to store current value of // energy at i'th checkpoint on street int currEnergy = 0; // flag to check if we have successfully crossed the // street without any energy loss < = o at any checkpoint bool flag = 0; // Traverse each check point lineraly for ( int i=0; i< n; i++) { currEnergy += arr[i]; // If current energy, becomes negative or 0, increment // initial minimum energy by the negative value plus 1. // to keep current energy positive (at least 1). Also // update current energy and flag. if (currEnergy < = 0) { initMinEnergy += abs (currEnergy) +1; currEnergy = 1; flag = 1; } }// If energy never became negative or 0, then // return 1. Else return computed initMinEnergy return (flag == 0)? 1 : initMinEnergy; }// Driver Program to test the case int main() { int arr[] = {4, -10, 4, 4, 4}; int n = sizeof (arr)/ sizeof (arr[0]); cout < < minInitialEnergy(arr, n); return 0; }

Java

// Java program to find minimum // initial energy to reach endclass GFG {// Function to calculate minimum // initial energy arr[] stores energy // at each checkpoints on street static int minInitialEnergy( int arr[], int n) { // initMinEnergy is variable to store // minimum initial energy required. int initMinEnergy = 0 ; // currEnergy is variable to store // current value of energy at // i'th checkpoint on street int currEnergy = 0 ; // flag to check if we have successfully // crossed the street without any energy // loss < = o at any checkpoint boolean flag = false ; // Traverse each check point lineraly for ( int i = 0 ; i < n; i++) { currEnergy += arr[i]; // If current energy, becomes negative or 0, // increment initial minimum energy by the negative // value plus 1. to keep current energy // positive (at least 1). Also // update current energy and flag. if (currEnergy < = 0 ) { initMinEnergy += Math.abs(currEnergy) + 1 ; currEnergy = 1 ; flag = true ; } }// If energy never became negative or 0, then // return 1. Else return computed initMinEnergy return (flag == false ) ? 1 : initMinEnergy; }// Driver code public static void main(String[] args) { int arr[] = { 4 , - 10 , 4 , 4 , 4 }; int n = arr.length; System.out.print(minInitialEnergy(arr, n)); } }// This code is contributed by Anant Agarwal.

python

# Python program to find mimimum initial enery to # reach end# Function to calculate minimum initial enery # arr[] stroes enery at each checkpoints on street def minInitialEnergy(arr): n = len (arr)# initMinEnergy is variable to store minimum initial # energy required initMinEnergy = 0 ; # currEnery is variable to store current value of # enery at i'th checkpoint on street currEnergy = 0 # flag to check if we have successfully crossed the # street without any energy loss < = 0 at any checkpoint flag = 0 # Traverse each check point linearly for i in range (n): currEnergy + = arr[i]# If current energy, becomes negative or 0, increment # initial minimum energy by the negative value plus 1. # to keep current energy positive (at least 1). Also # update current energy and flag. if currEnergy < = 0 : initMinEnergy + = ( abs (currEnergy) + 1 ) currEnergy = 1 flag = 1# If energy never became negative or 0, then # return 1. Else return computed initMinEnergy return 1 if flag = = 0 else initMinEnergy# Driver program to test above function arr = [ 4 , - 10 , 4 , 4 , 4 ] print minInitialEnergy(arr)# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

// C# program to find minimum // C# program to find minimum // initial energy to reach end using System; class GFG {// Function to calculate minimum // initial energy arr[] stores energy // at each checkpoints on street static int minInitialEnergy( int []arr, int n) {// initMinEnergy is variable to store // minimum initial energy required. int initMinEnergy = 0; // currEnergy is variable to store // current value of energy at // i'th checkpoint on street int currEnergy = 0; // flag to check if we have successfully // crossed the street without any energy // loss < = o at any checkpoint bool flag = false ; // Traverse each check point lineraly for ( int i = 0; i < n; i++) { currEnergy += arr[i]; // If current energy, becomes negative or 0, // negativeincrement initial minimum energy // by the value plus 1. to keep current // energy positive (at least 1). Also // update current energy and flag. if (currEnergy < = 0) { initMinEnergy += Math.Abs(currEnergy) + 1; currEnergy = 1; flag = true ; } }// If energy never became negative // or 0, then return 1. Else return // computed initMinEnergy return (flag == false ) ? 1 : initMinEnergy; }// Driver code public static void Main() { int []arr = {4, -10, 4, 4, 4}; int n = arr.Length; Console.Write(minInitialEnergy(arr, n)); } }// This code is contributed by Nitin Mittal.

的PHP

< ?php // PHP program to find minimum // initial energy to reach end// Function to calculate minimum // initial energy arr[] stores // energy at each checkpoints on street function minInitialEnergy( $arr , $n ) { // initMinEnergy is variable // to store minimum initial // energy required. $initMinEnergy = 0; // currEnergy is variable to // store current value of energy // at i'th checkpoint on street $currEnergy = 0; // flag to check if we have // successfully crossed the // street without any energy // loss < = o at any checkpoint $flag = 0; // Traverse each check // point lineraly for ( $i = 0; $i < $n ; $i ++) { $currEnergy += $arr [ $i ]; // If current energy, becomes // negative or 0, increment // initial minimum energy by // the negative value plus 1. // to keep current energy // positive (at least 1). Also // update current energy and flag. if ( $currEnergy < = 0) { $initMinEnergy += abs ( $currEnergy ) + 1; $currEnergy = 1; $flag = 1; } }// If energy never became // negative or 0, then // return 1. Else return // computed initMinEnergy return ( $flag == 0) ? 1 : $initMinEnergy ; }// Driver Code $arr = array (4, -10, 4, 4, 4); $n = sizeof( $arr ); echo minInitialEnergy( $arr , $n ); // This code is contributed // by nitin mittal. ?>

输出：