Мінімальне значення для отримання позитивного крок за кроком Сума рішення штрих-коду


Рівень складності Легко
Часто запитують у Свігі
масив

Постановка проблеми

У цій задачі нам дається послідовність чисел (може бути додатним від’ємним чи нульовим). Ми повинні взяти з собою ціле додатне число, а потім почнемо додавати всі цілі числа цього масив зліва направо з ним.
Ми хочемо мінімальне ціле додатне число, яке ми повинні взяти на початку, щоб у будь-який час наша поточна сума завжди залишалася додатною.

Приклад

nums = [-3,2,-3,4,2]
5

Пояснення:

Мінімальне значення для отримання позитивного крок за кроком Сума рішення штрих-коду
Тут ми бачимо, що якщо ми виберемо startValue = 5, то отримаємо всі проміжні суми додатними. Ми також можемо перевірити startValue = 4, що не є правильним рішенням.

nums = [1,2]
1

Пояснення:

Мінімальне стартове значення має бути позитивним.

Підхід

Припустимо, ми маємо масив, nums = [-3,2, -3,4,2]
Тепер, якщо ми вибрали початкове значення як 2 і продовжували додавати елементи зліва направо, тоді:

Мінімальне значення для отримання позитивного крок за кроком Сума рішення штрих-коду

У наведеному вище прикладі ми вибрали початкове значення як 2. Наша сума не буде залишатися позитивною кожного разу, тому нам потрібен якийсь більший елемент.

Нехай початковий вал дорівнює 5.
Мінімальне значення для отримання позитивного крок за кроком Сума рішення штрих-коду
Тепер ми чітко бачимо, що якщо початкове значення дорівнює 5, то ми напевно можемо подорожувати по масиву, зберігаючи постійну позитивну суму завжди. 5 може бути відповіддю, якщо це найменше ціле число, яке робить це.
Подумаймо про ситуацію, якщо ми вибрали val = 0 з нами на початку.

Мінімальне значення для отримання позитивного крок за кроком Сума рішення штрих-коду

Тепер, чи можемо ми сказати, що якщо ми подолаємо значення найбільш негативної поточної суми (-4 у поточному прикладі), то ми зможемо чітко передати масив без будь-яких проблем.
Як, у наведеному вище прикладі, найбільш негативним значенням є -4, щоб його подолати, ми повинні зробити його 1 (оскільки потрібно найменше ціле натуральне число).

Отже, ми хочемо, щоб значення 1 - (- 4) = 5 пройшло найбільш негативну ситуацію.
ми також бачили, що 5 може пройти рішення.

І якщо негативної поточної суми немає, ми просто виведемо 1, тому що хочемо позитивне інтегральне рішення.

Отже, наш алгоритм буде таким:

1. Нам потрібно шукати найбільш негативне рішення, тому ми перейдемо весь масив.
2. У кожній ітерації петля ми перевіримо, чи є поточна сума мінімальною чи ні, і відповідно оновимо наше мінімальне значення.
3. Нарешті, щоб зробити це найбільш негативне значення 1, ми просто віднімемо його від 1. (наприклад, якщо min = -4, val = 1 - (- 4) = 5).

Реалізація

Програма C ++ для мінімального значення, щоб отримати позитивний крок за кроком Сума рішення Leetcode

#include <iostream>
#include<vector>
using namespace std;

int minStartValue(vector<int>& nums) {
    
    int min=0,sum=0;
    for (int i = 0; i < nums.size(); i++){
        sum+=nums[i];
        min=min<sum?min:sum;
    }
    
    return 1-min;
}

int main() {
    vector<int> nums{-3,2,-3,4,2}; 
    cout<<minStartValue(nums)<<endl;	
  return 0;
}
5

Програма Java для мінімального значення, щоб отримати позитивний крок за кроком Сума рішення для штрих-коду

import java.util.*;

class Rextester{
    
    public static int minStartValue(int[] nums) 
    {
        Integer min=0,sum=0;
        for(int i:nums){
            sum+=i;
            min=Math.min(min,sum);
        }
        return 1-min;
    }
    
    public static void main(String args[])
    {
       	int[]nums={-3,2,-3,4,2};
        int ans=minStartValue(nums);
        System.out.println(ans);
    }
}
5

Аналіз складності для мінімального значення, щоб отримати позитивне покрокове рішення Leetcode Solution

Складність часу

O (n): Оскільки ми об’їжджаємо даний масив лінійно, отже, наша складність у часі буде O (n).

Складність простору 

O (1): Ми не використовували зайвий простір, тому наша космічна складність буде незмінною.