Energía inicial mínima requerida para cruzar la calle

Dada una array que contiene números positivos y negativos. La array representa los puntos de control de un extremo al otro de la calle. Los valores positivos y negativos representan la cantidad de energía en ese punto de control. Los números positivos aumentan la energía y los números negativos disminuyen. Encuentre la energía inicial mínima requerida para cruzar la calle de modo que el nivel de energía nunca llegue a 0 o sea inferior a 0.

Nota: El valor de la energía inicial mínima requerida será 1 incluso si cruzamos la calle con éxito sin perder energía a menos de 0 en ningún punto de control. El 1 es necesario para el punto de control inicial.

Ejemplos: 

Input : arr[] = {4, -10, 4, 4, 4}
Output: 7
Suppose initially we have energy = 0, now at 1st
checkpoint, we get 4. At 2nd checkpoint, energy gets
reduced 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 because
having 7 as initial energy value at 1st checkpoint
our 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: 1
We need at least 1 initial energy to reach first
checkpoint

Input : arr[] = {-1, -5, -9}
Output: 16

Tomamos la energía mínima inicial 0 es decir; initMinEnergy = 0 y energía en cualquier punto de control como currEnergy = 0. Ahora atraviese cada punto de control linealmente y agregue el nivel de energía en cada i-ésimo punto de control, es decir; energíaactual = energíaactual + arr[i]. Si currEnergy se vuelve no positivo, entonces necesitamos al menos «abs (currEnergy) + 1» energía inicial adicional para cruzar este punto. Por lo tanto, actualizamos initMinEnergy = (initMinEnergy + abs(currEnergy) + 1). También actualizamos currEnergy = 1 ya que ahora tenemos la energía inicial mínima adicional requerida para el siguiente punto.

A continuación se muestra la implementación de la idea anterior. 

// 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 linearly
    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 program to find minimum
// initial energy to reach end
 
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
    boolean flag = false;
 
    // Traverse each check point linearly
    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 program to find minimum initial energy to
# reach end
 
# Function to calculate minimum initial energy
# arr[] stores energy at each checkpoints on street
def minInitialEnergy(arr):
    n = len(arr)
     
    # 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 <= 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 linearly
    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 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 linearly
    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.
?>

<script>
// Javascript 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.
    let initMinEnergy = 0;
 
    // currEnergy is variable to
    // store current value of energy
    // at i'th checkpoint on street
    let currEnergy = 0;
 
    // flag to check if we have
    // successfully crossed the
    // street without any energy
    // loss <= o at any checkpoint
    let flag = 0;
 
    // Traverse each check
    // point linearly
    for (let 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 = 1;
        }
    }
 
    // If energy never became
    // negative or 0, then
    // return 1. Else return
    // computed initMinEnergy
    return (flag == 0) ? 1 : initMinEnergy;
}
 
// Driver Code
let arr = new Array(4, -10, 4, 4, 4);
let n = arr.length;
document.write(minInitialEnergy(arr, n));
 
// This code is contributed
// by Saurabh Jaiswal
</script>

7

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(1)

Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.