स्टक २ लेटकोड समाधान किन्नुहोस् र बेच्न उत्तम समय


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन डे श फेसबुक माइक्रोसफ्ट मोर्गन स्टेनले Uber
एरे लोभी

समस्या बयान

समस्यामा "बेच्ने समयको लागि किन्न र बिक्री स्टक २," मा हामीलाई एर्रे दिइन्छ जहाँ एर्रेमा प्रत्येक एलिमेन्टले त्यस दिन दिइएको स्टकको मूल्य समावेश गर्दछ।

को परिभाषा कारोबार शेयरको एक शेयर खरीद गर्दै छ र त्यो शेयरको एक शेयर बेच्दै छ।

हाम्रो कार्य भनेको तलका प्रतिबन्धहरूमा अधिकतम लाभ फेला पार्नु हो:

  1. हामी नयाँ स्टक किन्न सक्दैनौं यदि हामीले अघिल्लो स्टक बेचेका छैनौं भने। त्यो एक समयमा हामीसँग बढीमा एउटा स्टक हुन सक्छ।
  2. हामी सकेसम्म धेरै लेनदेन गर्न सक्छौं।

उदाहरणका

prices = [7,1,5,3,6,4]
7

व्याख्या: प्राप्त गर्न सकिने अधिकतम नाफा is हो। लेनदेनको विवरण निम्न छ:

पहिलो दिन: आराम गर्नुहोस्

दोस्रो दिन: किन्नुहोस्

तेस्रो दिन: बेच्नुहोस्

चौथो दिन: किन्नुहोस्

पाँचौं दिन: बेच्नुहोस्

छैठौं दिन: आराम गर्नुहोस्

स्टक २ लेटकोड समाधान किन्नुहोस् र बेच्न उत्तम समयको लागि दृष्टिकोण

हामीसँग लेनदेनको संख्यामा कुनै प्रतिबन्ध छैन त्यसैले हामी a को विचार गर्नेछौं लोभी एल्गोरिथ्म यहाँ त्यसैले प्रत्येक पटक हामी एक न्यूनतम मूल्य मा एक शेयर खरीद र अधिकतम मूल्य मा यो बेच्ने छ। हामी यसलाई संक्षेपमा भन्न सक्छौं, प्रत्येक मिनिमामा हामी एउटा स्टक किन्नेछौं र प्रत्येक मक्सीमामा हामी स्टक बेच्नेछौं। यो तल दिइएको चित्रमा वर्णन गरिएको छ। यो शेयर मूल्य र दिन बीचको एक प्लट हो। Letecode समाधान खरीद गर्नका लागि बेस्ट टाइम स्टक II

हामी यसलाई सरल बनाउन सक्छौं यदि हामीले देख्यौं कि एक maxima गठन हुन्छ जब सानो मानहरू मिनिमामा थपिन्छ। त्यसकारण अधिकतम लाभ गणना गर्न प्रत्येक मिनिमा र म्याक्सिमा ट्र्याक गरे पनि, हामी सिधै हाम्रो नाफामा ती मूल्यहरू थप्न सक्दछौं जसको लागि हामीले सकारात्मक ढलान भेट्टायौं जुन मूल्यहरू [i]> मूल्यहरू [i-1] हो। त्यस्ता सबै मानहरूको जोडले हामीलाई अधिकतम लाभ दिन्छ।

Letecode समाधान खरीद गर्नका लागि बेस्ट टाइम स्टक II

कार्यान्वयन

सी ++ कोड खरीद गर्नुहोस् र बेच्नको लागि उत्तम समय स्टॉक दोस्रो

#include <bits/stdc++.h> 
using namespace std; 
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
int main() 
{ 
 vector<int> arr = { 7,1,5,3,6,4 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
7

जापान कोड स्टक २ किन्नका लागि उत्तम समय को लागी

import java.util.Arrays; 
public class Tutorialcup {
     public static int maxProfit(int[] prices) {
        int ans = 0;
        int n=prices.length;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
  public static void main(String[] args) {
    int [] arr = {7,1,5,3,6,4}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
7

स्टक २ लेटकोड समाधान किन्नुहोस् र बेच्नको लागि उत्तम समयको जटिलता विश्लेषण

समय जटिलता

माथिको कोडको समय जटिलता हो ऊ) किनभने हामी एक पटक मात्र मूल्य एरे ट्र्याभर्स गर्दैछौं। यहाँ n मूल्य एरे को लम्बाई छ।

ठाउँ जटिलता

माथिको कोडको स्पेस जटिलता हो O (१) किनभने हामी केवल उत्तर भण्डारण गर्न मेमोरी प्रयोग गरिरहेका छौं।

सन्दर्भ