Минимална вредност за да се добие позитивно чекор по чекор сума Решение за лек-код


Ниво на тешкотија Лесно
Често прашувано во Swiggy
Низа

Изјава за проблем

Во овој проблем, ни е дадена низа од броеви (може да биде позитивна негативна или нула). Треба да земеме позитивен цел број со нас и тогаш ќе започнеме со додавање на сите цели броеви на ова низа од лево надесно со него.
Ние сакаме минимален позитивен цел број што треба да го земеме на почетокот, така што, во секое време, нашата сегашна сума секогаш ќе остане позитивна.

пример

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 може да биде одговорот ако е најмалиот цел број што го прави тоа.
Ајде да размислиме за ситуација ако избереме вал = 0 со нас на почетокот.

Минимална вредност за да се добие позитивно чекор по чекор сума Решение за лек-код

Сега, можеме ли да кажеме дека ако ја надминеме вредноста на повеќето негативни тековни суми (-4 во тековниот пример), тогаш можеме јасно да ја поминеме низата без никаков проблем.
Како во горниот пример, најнегативната вредност е -4, за да се надмине, треба да ја направиме 1 (затоа што е потребен најмал позитивен цел број).

Значи, сакаме вредноста 1 - (- 4) = 5 да ја помине најнегативната ситуација.
видовме и дека 5 можат да го поминат решението.

И ако нема негативна тековна сума, ние само ќе излеземе 1 затоа што сакаме позитивно интегрално решение.

Значи, нашиот алгоритам ќе биде:

1. Треба да бараме најнегативно решение, така што ќе ја поминеме целата низа.
2. Во секоја повторување на јамка ќе провериме дали тековната сума е минимална или не и соодветно ќе ја ажурираме нашата минимална вредност.
3. Конечно, за да ја направиме оваа најнегативна вредност на 1, ние само ќе ја одземеме од 1. (на пр., Ако мин = -4, вал = 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

Јава програма за минимална вредност за да се добие позитивно чекор по чекор сума Решение за 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).

Комплексноста на просторот 

О (1): Не користевме дополнителен простор, така што нашата вселенска сложеност ќе биде постојана.