Мінімальнае значэнне для атрымання станоўчага рашэння крок за крокам


Узровень складанасці Лёгка
Часта пытаюцца ў Swiggy
масіў

Пастаноўка праблемы

У гэтай задачы нам даецца паслядоўнасць лікаў (можа быць дадатным адмоўным альбо нулявым). Мы павінны ўзяць з сабой дадатнае цэлае лік, а потым пачнем дадаваць усе цэлыя лікі гэтага масіў злева направа з ім.
Мы хочам мінімальнага дадатнага цэлага ліку, якое мы павінны ўзяць у пачатку, каб у любы час наша бягучая сума заўсёды заставалася дадатнай.

Прыклад

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

Тлумачэнне:

Мінімальнае значэнне для атрымання станоўчага рашэння крок за крокам
Тут мы бачым, што калі выбраць startValue = 5, мы атрымаем станоўчую прамежкавую суму. Мы таксама можам праверыць, ці ёсць startValue = 4, што не з'яўляецца правільным рашэннем.

nums = [1,2]
1

Тлумачэнне:

Мінімальнае значэнне старту павінна быць дадатным.

Падыход

Дапусцім, у нас масіў, nums = [-3,2, -3,4,2]
Цяпер, калі мы выбіраем пачатковае значэнне як 2 і працягваем дадаваць элементы злева направа, тады:

Мінімальнае значэнне для атрымання станоўчага рашэння крок за крокам

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

Няхай пачатковы val будзе 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 ++ для мінімальнага значэння, каб атрымаць станоўчае рашэнне крок за крокам

#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 для мінімальнага значэння для атрымання станоўчага станоўчага рашэння Leetcode

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

Складанасць часу

O (n): Таму што мы перамяшчаем дадзены масіў лінейна, таму наша складанасць у часе будзе O (n).

Касмічная складанасць 

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