Valor mínimo que se agregará a las sumas de prefijos en cada índice de array para que sean positivos

Dada una array arr [] que consta de N números enteros, la tarea es encontrar el valor positivo mínimo S que debe agregarse de modo que la suma del prefijo en cada índice de la array dada después de agregar S sea siempre positiva.

Ejemplos: 

Entrada: arr[] = {-3, 2, -3, 4, 2}
Salida: 5
Explicación:
Para S = 5, las sumas de prefijos en cada índice de array son las siguientes:
En el índice 1: (5 – 3) = 2
En el índice 2: (2 + 2) = 4
En el índice 3: (4 – 3) = 1
En el índice 4: (1 + 4) = 5
En el índice 5: (5 + 2) = 7
Dado que todos los prefijos se suman es mayor que 0, la respuesta requerida es 5.

Entrada: arr[] = {1, 2}
Salida: 1

Enfoque ingenuo: el enfoque más simple es iterar sobre todos los valores posibles de S a partir de 1 y agregar S a la suma del prefijo en cada índice de array y verificar si es mayor que 0 o no. Imprima el valor de S para el cual todas las sumas de los prefijos resultan positivas.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación:

• Inicialice una variable minValue con 0 para almacenar la suma mínima del prefijo.
• Inicialice una suma variable para almacenar la suma del prefijo en cada índice.
• Recorra la array arr[] sobre el rango [0, N – 1] usando la variable i .
  • Actualice la suma y agregue arr[i] a la suma .
  • Si sum es menor que minValue , establezca minValue como sum .
• Inicialice una variable startValue para almacenar el resultado deseado y establezca startValue igual a (1 – minValue) .
• Después de los pasos anteriores, imprima el valor de startValue como el valor mínimo posible de S .

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum startValue
// for positive prefix sum at each index
int minStartValue(vector<int>& nums)
{
    // Store the minimum prefix sum
    int minValue = 0;
 
    // Stores prefix sum at each index
    int sum = 0;
 
    // Traverse over the array
    for (auto n : nums) {
 
        // Update the prefix sum
        sum += n;
 
        // Update the minValue
        minValue = min(minValue, sum);
    }
 
    int startValue = 1 - minValue;
 
    // Return the positive start value
    return startValue;
}
 
// Driver Code
int main()
{
    vector<int> nums = { -3, 2, -3, 4, 2 };
 
    // Function Call
    cout << minStartValue(nums);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
 
class GFG{
 
// Function to find minimum startValue
// for positive prefix sum at each index
static int minStartValue(int[] nums)
{
     
    // Store the minimum prefix sum
    int minValue = 0;
  
    // Stores prefix sum at each index
    int sum = 0;
     
    // Traverse over the array
    for(int n : nums)
    {
         
        // Update the prefix sum
        sum += n;
         
        // Update the minValue
        minValue = Math.min(minValue, sum);
    }
     
    int startValue = 1 - minValue;
     
    // Return the positive start value
    return startValue;
}
  
// Driver Code
public static void main(String[] args)
{
    int[] nums = { -3, 2, -3, 4, 2 };
  
    // Function Call
    System.out.println(minStartValue(nums));
}
}
 
// This code is contributed by susmitakundugoaldanga

# Python3 program for the
# above approach
 
# Function to find minimum startValue
# for positive prefix sum at each index
def minStartValue(nums):
   
    # Store the minimum prefix sum
    minValue = 0
 
    # Stores prefix sum at each index
    sum = 0
 
    # Traverse over the array
    for i in range(len(nums)):
       
        # Update the prefix sum
        sum += nums[i]
 
        # Update the minValue
        minValue = min(minValue, sum)
 
    startValue = 1 - minValue
     
    # Return the positive start value
    return startValue
 
# Driver Code
if __name__ == '__main__':
   
    nums = [ -3, 2, -3, 4, 2 ]
     
    # Function Call
    print(minStartValue(nums))
 
# This code is contributed by Princi Singh

// C# program for the above approach
using System;
  
class GFG{
   
// Function to find minimum startValue
// for positive prefix sum at each index
static int minStartValue(int[] nums)
{
      
    // Store the minimum prefix sum
    int minValue = 0;
   
    // Stores prefix sum at each index
    int sum = 0;
      
    // Traverse over the array
    foreach(int n in nums)
    {
          
        // Update the prefix sum
        sum += n;
          
        // Update the minValue
        minValue = Math.Min(minValue, sum);
    }
      
    int startValue = 1 - minValue;
      
    // Return the positive start value
    return startValue;
}
   
// Driver Code
public static void Main()
{
    int[] nums = { -3, 2, -3, 4, 2 };
   
    // Function Call
    Console.WriteLine(minStartValue(nums));
}
}
 
// This code is contributed by code_hunt

<script>
// Javascript program for the above approach
 
// Function to find minimum startValue
// for positive prefix sum at each index
function minStartValue(nums)
{
 
    // Store the minimum prefix sum
    let minValue = 0;
 
    // Stores prefix sum at each index
    let sum = 0;
 
    // Traverse over the array
    for (let n = 0; n < nums.length; n++) {
 
        // Update the prefix sum
        sum += nums[n];
 
        // Update the minValue
        minValue = Math.min(minValue, sum);
    }
    let startValue = 1 - minValue;
 
    // Return the positive start value
    return startValue;
}
 
// Driver Code
    let nums = [ -3, 2, -3, 4, 2 ];
 
    // Function Call
    document.write(minStartValue(nums));
     
    // This code is contributed by souravmahato348.
</script>

5

Complejidad temporal: O(N)
Espacio auxiliar: O(1)