Նվազագույն արժեքը քայլ առ քայլ գումար ստանալու համար Leetcode լուծում գումար


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Swiggy
Դասավորություն

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրված է թվերի հաջորդականություն (կարող է լինել դրական բացասական կամ զրո): Մենք պետք է մեզ հետ վերցնենք դրական ամբողջ թիվ, և ապա մենք կսկսենք ավելացնել այս բոլոր ամբողջ թվերը դասավորություն ձախից աջ դրանով:
Մենք ուզում ենք նվազագույն դրական ամբողջ թիվ, որը պետք է վերցնենք սկզբում, որպեսզի ցանկացած պահի մեր ընթացիկ գումարը միշտ մնա դրական:

Օրինակ

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

Բացատրությունը.

Նվազագույն արժեքը քայլ առ քայլ գումար ստանալու համար Leetcode լուծում գումար
Այստեղ մենք կարող ենք տեսնել, որ եթե startValue = 5 ընտրենք, մենք ստանում ենք բոլոր միջանկյալ գումարի դրական ցուցանիշները: Կարող ենք նաև ստուգել startValue = 4-ը, ինչը ճիշտ լուծում չէ:

nums = [1,2]
1

Բացատրությունը.

Նվազագույն մեկնարկային արժեքը պետք է դրական լինի:

Մոտեցում

Ենթադրենք, մենք ունենք զանգված, nums = [-3,2, -3,4,2]
Եթե ​​մենք սկզբնական արժեքը ընտրում ենք որպես 2, և շարունակում ենք տարրեր ավելացնել ձախից աջ, ապա ՝

Նվազագույն արժեքը քայլ առ քայլ գումար ստանալու համար Leetcode լուծում գումար

Վերոնշյալ օրինակում մենք սկզբնական արժեքը ընտրել ենք որպես 2. Մեր գումարն ամեն անգամ դրական չի մնա, ուստի մեզ ավելի մեծ տարր է պետք:

Թող նախնական արժեքը լինի 5:
Նվազագույն արժեքը քայլ առ քայլ գումար ստանալու համար Leetcode լուծում գումար
Այժմ, մենք հստակ կարող ենք տեսնել, որ եթե սկզբնական արժեքը 5 է, ապա մենք, անկասկած, կարող ենք ճանապարհորդել ամբողջ զանգվածում ՝ միշտ պահպանելով մեր ընթացիկ գումարը դրական: 5-ը կարող է լինել պատասխան, եթե դա անում է ամենափոքր ամբողջ թիվը:
Եկեք մտածենք իրավիճակի մասին, եթե սկզբում մեզ հետ ընտրենք val = 0:

Նվազագույն արժեքը քայլ առ քայլ գումար ստանալու համար Leetcode լուծում գումար

Հիմա կարո՞ղ ենք ասել, որ եթե հաղթահարենք առավելագույն բացասական ընթացիկ գումարի արժեքը (-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 ծրագիր ՝ նվազագույն արժեքի համար, քայլ առ քայլ դրական ստանալու համար 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 լուծում

Timeամանակի բարդություն

Վրա): Քանի որ, մենք գծի վրայով անցնում ենք տրված զանգվածը, ուստի մեր ժամանակի բարդությունը կլինի O (n):

Տիեզերական բարդություն 

O (1): Մենք ոչ մի լրացուցիչ տարածք չենք օգտագործել, ուստի մեր տիեզերական բարդությունը կլինի անընդհատ: