מינימום ווערט צו באַקומען positive שריט דורך שריט סאַם לעעטקאָדע לייזונג


שוועריקייט לעוועל גרינג
אָפט געבעטן אין סוויגגי
מענגע

פּראָבלעם סטאַטעמענט

אין דעם פּראָבלעם, מיר געבן אַ סיקוואַנס פון נומערן (קען זיין positive נעגאַטיוו אָדער נול). מיר מוזן נעמען אַ positive ינטאַדזשער מיט אונדז און מיר וועלן אָנהייבן צו לייגן אַלע ינטאַדזשערז פון דעם מענגע פון לינקס צו רעכט מיט אים.
מיר וועלן די מינימום positive ינטאַדזשער וואָס מיר זאָל נעמען אין די אָנהייב, אַזוי אַז אונדזער קראַנט סומע וועט שטענדיק בלייבן positive.

בייַשפּיל

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

דערקלערונג:

מינימום ווערט צו באַקומען positive שריט דורך שריט סאַם לעעטקאָדע לייזונג
מיר קענען זען אַז אויב מיר קלייַבן startValue = 5, מיר באַקומען אַלע ינטערמידייט סאַכאַקל positive. מיר קענען אויך קאָנטראָלירן פֿאַר startValue = 4, וואָס איז נישט ריכטיק לייזונג.

nums = [1,2]
1

דערקלערונג:

מינימום אָנהייב ווערט זאָל זיין positive.

צוגאַנג

רעכן מיר האָבן מענגע, נומס = [-3,2, -3,4,2]
איצט אויב מיר קלייַבן ערשט ווערט ווי 2 און האַלטן אַדינג עלעמענטן פֿון לינקס צו רעכט, דעמאָלט:

מינימום ווערט צו באַקומען positive שריט דורך שריט סאַם לעעטקאָדע לייזונג

אין דעם ביישפּיל, מיר האָבן אויסדערוויילט די ערשטע ווערט ווי 2. אונדזער סומע וועט נישט בלייבן positive יעדער מאָל, אַזוי מיר דאַרפֿן אַ גרעסערע עלעמענט.

לאָזן די ערשט ווערט 5.
מינימום ווערט צו באַקומען positive שריט דורך שריט סאַם לעעטקאָדע לייזונג
איצט מיר קענען קלאר זען אַז אויב די סטאַרטינג ווערט איז 5, מיר קענען שורלי אַרומפאָרן איבער די מענגע בעכעסקעם אונדזער קראַנט סומע שטענדיק positive. 5 קען זיין דער ענטפער אויב דאָס איז דער קלענסטער ינטאַדזשער.
זאל ס טראַכטן פון אַ סיטואַציע אויב מיר קלייַבן val = 0 מיט אונדז אין די אָנהייב.

מינימום ווערט צו באַקומען positive שריט דורך שריט סאַם לעעטקאָדע לייזונג

קענען מיר איצט זאָגן אַז אויב מיר באַקומען די ווערט פון די מערסט נעגאַטיוו קראַנט סומע (-4 אין קראַנט בייַשפּיל), מיר קענען קלאר פאָרן די מענגע אָן קיין פּראָבלעם.
ווי, אין אויבן ביישפּיל, די מערסט נעגאַטיוו ווערט איז -4. צו באַקומען עס, מיר האָבן צו מאַכן עס 1 (ווייַל, קלענסטער positive ינטאַדזשער דארף).

אַזוי מיר וועלן ווערט 1 - (- 4) = 5 צו פאָרן די מערסט נעגאַטיוו סיטואַציע.
מיר האָבן אויך געזען אַז 5 קענען פאָרן די לייזונג.

און אויב עס איז קיין נעגאַטיוו קראַנט סומע, מיר וועלן נאָר רעזולטאַט 1 ווייַל מיר וועלן אַ positive ינטאַגראַל לייזונג.

אַזוי, אונדזער אַלגערידאַם וועט זיין:

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

Java פּראָגראַם פֿאַר מינימום ווערט צו באַקומען positive סעט לעעטקאָדע סאַלושאַן

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר מינימום ווערט צו באַקומען אַ positive שריט דורך שריט סאַם לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (n): ווייַל מיר פאָרן די געגעבן מענגע לינעאַרלי, אַזוי אונדזער קאַמפּלעקסיטי איז אָ (n).

ספעיס קאַמפּלעקסיטי 

אָ (1): מיר האָבן נישט געניצט אַן עקסטרע פּלאַץ, אַזוי אונדזער פּלאַץ קאַמפּלעקסיטי וועט זיין קעסיידערדיק.