د مرحلې Sum لیټکوډ حل لخوا مثبت ګام ترلاسه کولو لپاره لږترلږه ارزښت


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي سویګی
پیشه

ستونزه بیان

پدې ستونزه کې ، موږ د شمیرو ترتیب ورکول کیږي (ممکن مثبت منفي یا صفر وي). موږ باید له موږ سره مثبته عدد ولرو او بیا به موږ د دې ټولې انګېزې اضافه کړو سور له کي left نه ښي سره.
موږ لږترلږه مثبت عدد وغواړو چې موږ یې باید په پیل کې واخلو ، نو له همدې امله زموږ په اوسني رقم کې تل مثبت پاتې کیږي.

بېلګه

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

وضاحت:

د مرحلې Sum لیټکوډ حل لخوا مثبت ګام ترلاسه کولو لپاره لږترلږه ارزښت
موږ دلته لیدلی شو چې که موږ startValue = 5 غوره کړو ، موږ ټول منځمهاله مثبت ترلاسه کوو. موږ کولی شو د startValue = 4 لپاره هم وګورو ، کوم چې سم حل ندی.

nums = [1,2]
1

وضاحت:

د پیل لږترلږه باید مثبت وي.

او کړنلاره

فرض کړئ ، موږ صفونه لرو ، شمیرونه = [-3,2،3,4,2، -XNUMX،XNUMX،XNUMX]
اوس که موږ ابتدايي ارزښت د 2 په توګه غوره کړو ، او له کی from څخه ښیې څخه عناصر اضافه کولو ته دوام ورکوو ، نو بیا:

د مرحلې Sum لیټکوډ حل لخوا مثبت ګام ترلاسه کولو لپاره لږترلږه ارزښت

په پورتني مثال کې ، موږ ابتدايي ارزښت د 2 په توګه ټاکلی دی. زموږ رقم به هر ځل مثبت پاتې نشي ، نو موږ ځینې لوی عنصر ته اړتیا لرو.

پریږدئ چې لومړنی ویل 5 وي.
د مرحلې Sum لیټکوډ حل لخوا مثبت ګام ترلاسه کولو لپاره لږترلږه ارزښت
اوس ، موږ کولی شو په څرګنده توګه وګورو چې که چیرې د پیل ارزښت 5 بیا وي نو موږ حتما کولی شو زموږ د اوسني پیسو مثبت ساتلو لپاره د صف په اوږدو کې سفر وکړو. 5 کیدی شي ځواب وي که چیرې دا کوچنۍ کوچنۍ انفرادي وي.
راځئ د یو حالت په اړه فکر وکړو که موږ په پیل کې زموږ سره والو = 0 غوره کړو.

د مرحلې Sum لیټکوډ حل لخوا مثبت ګام ترلاسه کولو لپاره لږترلږه ارزښت

اوس ، ایا موږ کولی شو ووایو که چیرې موږ د ډیری منفي موجوده مجموعې ارزښت باندې بریالي شو (په اوسني مثال کې -4) ، نو موږ کولی شو پرته له کومې ستونزې په صف کې تیر شو.
لکه ، په پورتنۍ مثال کې ، خورا منفي ارزښت -4 دی ، د دې د بریالي کولو لپاره ، موږ باید دا 1 کړئ (ځکه چې ، کوچني مثبت انډیجر ته اړتیا ده).

نو موږ د خورا منفي حالت تیریدو لپاره 1 - (- 4) = 5 ارزښت غواړو.
موږ دا هم لیدلي چې 5 کولی شي حل حل کړي.

او که چیرې هیڅ منفي اوسنۍ رقم شتون ونلري ، نو موږ به یې یوازې 1 تولید کړو ځکه چې موږ مثبت بشپړ حل غواړو.

نو ، زموږ الګوریتم به دا وي:

1. موږ باید د ډیری منفي حل په لټه کې شو ، نو موږ به ټول صف تیر کړو.
د. په هر تکرار کې لوپ موږ به وګورو چې آیا اوسنۍ اندازه لږترلږه ده که نه او موږ به د هغې مطابق زموږ دقیق ارزښت تازه کړو.
3. په پای کې د دې خورا منفي ارزښت رامینځته کولو لپاره ، موږ به دا له 1 څخه منفي کړو. (د مثال په توګه که من = -1 ، ویل = 4 - (- 1) = 4).

تطبیق

C ++ د لږترلږه ارزښت لپاره برنامه د مرحلې Sum لیټکوډ حل لخوا مثبت ګام ترلاسه کول

#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

د مرحلې Sum لیټکوډ حل لخوا مثبت ګام ترلاسه کولو لپاره د لږترلږه ارزښت لپاره جاوا پروګرام

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

د مرحلې Sum Leetcode حل لخوا مثبت ګام ترلاسه کولو لپاره د لږترلږه ارزښت لپاره د پیچلو تحلیل

د وخت پیچلتیا

O (n): ځکه چې ، موږ ورکړل شوي صف په خطي توګه تیروو ، پدې توګه زموږ د وخت پیچلتیا به O (n) وي.

د ځای پیچلتیا 

O (1): موږ کوم اضافي ځای نه دی کارولی ، نو پدې توګه به زموږ د ځای پیچلتیا دوام ولري.