படி தொகை லீட்கோட் தீர்வு மூலம் நேர்மறையான படி பெற குறைந்தபட்ச மதிப்பு  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது Swiggy
அணி குறியீட்டு பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions

சிக்கல் அறிக்கை  

இந்த சிக்கலில், எண்களின் வரிசை எங்களுக்கு வழங்கப்படுகிறது (நேர்மறை எதிர்மறை அல்லது பூஜ்ஜியமாக இருக்கலாம்). எங்களுடன் நேர்மறையான முழு எண்ணை எடுக்க வேண்டும், பின்னர் இதன் முழு எண்களையும் சேர்க்கத் தொடங்குவோம் வரிசை அதனுடன் இடமிருந்து வலமாக.
தொடக்கத்தில் நாம் எடுக்க வேண்டிய குறைந்தபட்ச நேர்மறை முழு எண்ணை நாங்கள் விரும்புகிறோம், இதனால், எந்த நேரத்திலும் எங்கள் தற்போதைய தொகை எப்போதும் நேர்மறையாக இருக்கும்.

உதாரணமாக

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

விளக்கம்:

படி தொகை லீட்கோட் தீர்வு மூலம் நேர்மறையான படி பெற குறைந்தபட்ச மதிப்பு
StartValue = 5 ஐத் தேர்வுசெய்தால், எல்லா இடைநிலை தொகையும் நேர்மறையாகப் பெறுவதை இங்கே காணலாம். StartValue = 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) ஆக இருக்கும்.

மேலும் காண்க
OSI மாதிரி

விண்வெளி சிக்கலானது 

ஓ (1): நாங்கள் எந்த கூடுதல் இடத்தையும் பயன்படுத்தவில்லை, இதனால் எங்கள் இட சிக்கலானது நிலையானதாக இருக்கும்.

1