స్టెప్ సమ్ లీట్‌కోడ్ సొల్యూషన్ ద్వారా సానుకూల దశను పొందడానికి కనీస విలువ


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Swiggy
అర్రే

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు సంఖ్యల క్రమం ఇవ్వబడుతుంది (సానుకూల ప్రతికూల లేదా సున్నా కావచ్చు). మేము మాతో సానుకూల పూర్ణాంకం తీసుకోవాలి, ఆపై దీని యొక్క పూర్ణాంకాలను జోడించడం ప్రారంభిస్తాము అమరిక దానితో ఎడమ నుండి కుడికి.
మేము ప్రారంభంలో తీసుకోవలసిన కనీస సానుకూల పూర్ణాంకం కావాలి, తద్వారా ఎప్పుడైనా మా ప్రస్తుత మొత్తం ఎల్లప్పుడూ సానుకూలంగా ఉంటుంది.

ఉదాహరణ

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

వివరణ:

స్టెప్ సమ్ లీట్‌కోడ్ సొల్యూషన్ ద్వారా సానుకూల దశను పొందడానికి కనీస విలువ
మేము startValue = 5 ను ఎంచుకుంటే, మనకు అన్ని ఇంటర్మీడియట్ మొత్తం పాజిటివ్ అవుతుంది. మేము స్టార్ట్‌వాల్యూ = 4 కోసం కూడా తనిఖీ చేయవచ్చు, ఇది సరైన పరిష్కారం కాదు.

nums = [1,2]
1

వివరణ:

కనీస ప్రారంభ విలువ సానుకూలంగా ఉండాలి.

అప్రోచ్

మనకు శ్రేణి ఉందని అనుకుందాం, సంఖ్యలు = [-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 నుండి తీసివేస్తాము. (ఉదా. నిమిషం = -4, వాల్ = 1 - (- 4) = 5).

అమలు

స్టెప్ సమ్ లీట్‌కోడ్ సొల్యూషన్ ద్వారా సానుకూల దశను పొందడానికి కనీస విలువ కోసం సి ++ ప్రోగ్రామ్

#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

స్టెప్ సమ్ లీట్‌కోడ్ సొల్యూషన్ ద్వారా సానుకూల దశను పొందడానికి కనీస విలువ కోసం జావా ప్రోగ్రామ్

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

స్టెప్ సమ్ లీట్‌కోడ్ సొల్యూషన్ ద్వారా సానుకూల దశను పొందడానికి కనీస విలువ కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై): ఎందుకంటే, మేము ఇచ్చిన శ్రేణిని సరళంగా ప్రయాణిస్తున్నాము, అందువల్ల మన సమయ సంక్లిష్టత O (n) అవుతుంది.

అంతరిక్ష సంక్లిష్టత 

ఓ (1): మేము అదనపు స్థలాన్ని ఉపయోగించలేదు, అందువల్ల మా స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.