स्टॉक II लीटकोड सोल्यूशन खरेदी आणि विक्री करण्याचा सर्वोत्तम वेळ


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन डीई शॉ फेसबुक मायक्रोसॉफ्ट मॉर्गन स्टॅन्ले उबेर
अरे लोभी

समस्या विधान

“स्टॉक II खरेदी करण्याचा सर्वोत्तम वेळ” या समस्येमध्ये आम्हाला अ‍ॅरे दिला जातो जिथे अ‍ॅरेमधील प्रत्येक घटकास त्या दिवशी दिलेल्या स्टॉकची किंमत असते.

ची व्याख्या व्यवहार स्टॉकचा एक हिस्सा विकत घेत आहे आणि त्या समभावाचा एक हिस्सा विकत आहे.

आमचे कार्य पुढील प्रतिबंधांनुसार जास्तीत जास्त नफा शोधणे आहे:

  1. आम्ही मागील स्टॉक विकला नाही तर आम्ही नवीन स्टॉक खरेदी करू शकत नाही. आपल्याकडे जास्तीत जास्त एक स्टॉक असू शकतो.
  2. आम्हाला पाहिजे तितके व्यवहार करता येतात.

उदाहरण

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

स्पष्टीकरण: मिळवता येणारा जास्तीत जास्त नफा is आहे. व्यवहाराचा तपशील खालीलप्रमाणेः

पहिला दिवस: विश्रांती

दुसरा दिवस: खरेदी करा

तिसरा दिवस: विक्री

चौथा दिवस: खरेदी करा

पाचवा दिवस: विक्री

सहावा दिवस: विश्रांती

स्टॉक II लीटकोड सोल्यूशन खरेदी आणि विक्रीसाठी सर्वोत्कृष्ट वेळेचा दृष्टीकोन

आपल्याकडे व्यवहाराच्या संख्येवर कोणतेही बंधन नसल्यामुळे आम्ही अ लोभी अल्गोरिदम येथे. म्हणून प्रत्येक वेळी आम्ही कमी किंमतीत स्टॉक विकत घेऊ आणि जास्तीत जास्त किंमतीवर विक्री करू. आम्ही त्याचा सारांश देऊ शकतो, प्रत्येक मिनिमावर आम्ही एक स्टॉक विकत घेऊ आणि प्रत्येक मॅक्सिमावर आम्ही स्टॉक विकू. खाली दिलेल्या आकृतीमध्ये हे स्पष्ट केले आहे. दिवसातील किंमती आणि दिवस यांच्यातला हा प्लॉट आहे. स्टॉक विकत घेण्यासाठी व विक्री करण्याचा सर्वोत्तम वेळ लीटकोड सोल्यूशन II

जेव्हा मिनीमामध्ये लहान व्हॅल्यूज जोडली जातात तेव्हा मॅक्सिमा तयार केली गेली तर आपण हे सुलभ करू शकतो. म्हणून जास्तीत जास्त नफा मोजण्यासाठी प्रत्येक मिनीमा आणि मॅक्सिमाचा मागोवा घेत असूनही, आम्ही थेट आपल्या नफ्यात ती मूल्ये जोडू शकतो ज्यासाठी आम्हाला सकारात्मक उतार सापडला ज्या किंमती आहेत [i]> किंमती [i-1]. अशा सर्व मूल्यांची जोड आपल्याला अधिकाधिक नफा देईल.

स्टॉक विकत घेण्यासाठी व विक्री करण्याचा सर्वोत्तम वेळ लीटकोड सोल्यूशन II

अंमलबजावणी

स्टॉक विकत घेण्यासाठी आणि विक्री करण्यासाठी सर्वोत्कृष्ट वेळेसाठी सी ++ कोड 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

स्टॉक विकत घेण्यासाठी आणि विक्री करण्यासाठी सर्वोत्कृष्ट वेळेसाठी जावा कोड II

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

स्टॉक II लीटकोड सोल्यूशन खरेदी आणि विक्रीसाठी सर्वोत्तम वेळेचे जटिलता विश्लेषण

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे O (n) कारण आम्ही फक्त एकदाच किंमतीच्या अ‍ॅरेसीचा मागोवा घेत आहोत. येथे एन किंमत अ‍ॅरेची लांबी आहे.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे ओ (1) कारण आम्ही फक्त उत्तर संग्रहित करण्यासाठी मेमरी वापरत आहोत.

संदर्भ