স্টক তৃতীয় লেটকোড সলিউশন কেনা বেচার সেরা সময়


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক
বিন্যাস ডায়নামিক প্রোগ্রামিং

সমস্যা বিবৃতি

"বেস্ট টাইম টু বেস্ট বেস্ট বেস্ট টাইম" সমস্যাটিতে আমাদের একটি অ্যারে দেওয়া হয় যেখানে অ্যারের প্রতিটি উপাদান সেই দিন প্রদত্ত স্টকের দাম ধারণ করে।

সংজ্ঞা লেনদেন শেয়ারের এক ভাগ কিনছে এবং সেই শেয়ারের এক ভাগ বিক্রয় করছে।

আমাদের কাজটি নিম্নলিখিত বিধিনিষেধের আওতায় সর্বাধিক মুনাফা অর্জন করা:

  1. আমরা আগের শেয়ারটি বিক্রি না করে আমরা একটি নতুন স্টক কিনতে পারি না buy এটি এমন একটি সময়ে আমাদের সর্বাধিক একটি স্টক থাকতে পারে।
  2. আমরা সর্বাধিক দুটি লেনদেন করতে পারি।

উদাহরণ

prices = [1,2,3,4,5]
4

ব্যাখ্যা: প্রাপ্ত সর্বাধিক মুনাফা 4 হয় লেনদেনের বিশদ:

প্রথম দিন: কিনুন

দ্বিতীয় দিন: বিশ্রাম

তৃতীয় দিন: বিশ্রাম

চতুর্থ দিন: বিশ্রাম

পঞ্চম দিন: বিক্রয়

স্টক তৃতীয় লেটকোড সলিউশন কেনার এবং বেচার জন্য সেরা সময়টির জন্য পন্থা

এই সমস্যাটির একটি হার্ড সংস্করণ শেয়ার কেনার এবং বেচার সেরা সময়। সুতরাং এই সমস্যাটিতে ঝাঁপ দেওয়ার আগে অবশ্যই সমস্যার সহজ সংস্করণটি সমাধান করতে হবে।

সহজ সংস্করণের তুলনায় যেখানে আমরা এখানে কেবল একটি লেনদেন করতে পারি, আমরা সর্বাধিক দুটি লেনদেন করতে পারি। যার অর্থ একটি লেনদেন বা দুটি লেনদেন এমনভাবে হয় যাতে সর্বোচ্চ লাভ হয়।

সমস্যার সবচেয়ে জটিল অংশটি হ'ল দ্বিতীয় লেনদেন কীভাবে পরিচালনা করতে হয়। একবার এই সমস্যাটি দেখার জন্য আমরা আমাদের দৃষ্টিভঙ্গি পরিবর্তন করি, এই সমস্যাটিকে এই সমস্যার একটি সহজ সংস্করণে রূপান্তর করা যেতে পারে।

ধরা যাক আমরা 200 টাকার লাভের সাথে আমাদের প্রথম লেনদেন শেষ করেছি। (এই অংশটি সমান শেয়ার কেনার এবং বেচার সেরা সময়)। সুতরাং প্রথম লেনদেনের পরে, আমাদের হাতে 200 টাকা রয়েছে।

এখন আমরা যখন 500 টাকার স্টক কিনতে যাই। আমরা এটির মতো ভাবতে পারি, যদিও স্টকের দাম 500 রুপি। তবে আমাদের জন্য, এটি 300 রুপি কারণ আমাদের হাতে ইতিমধ্যে 200 রুপি রয়েছে এবং আমরা এটি বিনামূল্যে পেয়েছি। এখন আমরা দ্বিতীয় লেনদেনটি এমনভাবে করবো যাতে নেট মুনাফাটি আমরা যেমন করেছিলাম তেমনভাবেই বাড়ানো যায় শেয়ার কেনার এবং বেচার সেরা সময় সমস্যা.

পদ্ধতির এই উদাহরণ থেকে আরও স্পষ্ট হবে:

স্টক কেনার এবং বেচার সেরা সময়টির জন্য লেটকোড সমাধান I

বাস্তবায়ন

স্টক কেনার এবং বেচার সেরা সময় জন্য জাভা কোড III

import java.util.Arrays; 
public class Tutorialcup {
    public static int maxProfit(int[] prices) {
  int firstSell = 0;
  int secondSell = 0;
  int firstBuy = Integer.MAX_VALUE;
  int secondBuy = Integer.MAX_VALUE;
  for(int i = 0; i < prices.length; i++) {
    int p = prices[i];
    firstBuy = Math.min(firstBuy, p);
    firstSell = Math.max(firstSell, p - firstBuy);
    secondBuy = Math.min(secondBuy, p - firstSell);
    secondSell = Math.max(secondSell, p - secondBuy);
  }
  
  return secondSell;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
4

স্টক কেনার এবং বেচার সেরা সময় দেওয়ার জন্য সি ++ কোড III

#include <bits/stdc++.h> 
using namespace std; 
     int maxProfit(vector<int>& prices) {
  int firstSell = 0;//stores profit after one sell
  int secondSell = 0;//stores profit after two sell
  int firstBuy = INT_MAX;
  int secondBuy = INT_MAX;
  int n=prices.size();
        for(int i=0;i<n;i++)
        {
            firstBuy=min(firstBuy,prices[i]);
            firstSell=max(firstSell,prices[i]-firstBuy);
            secondBuy=min(secondBuy,prices[i]-firstSell);
            secondSell=max(secondSell,prices[i]-secondBuy); 
        }
        return secondSell;
    }
int main() 
{ 
 vector<int> arr = { 1,2,3,4,5 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
4

স্টক তৃতীয় লেটকোড সলিউশন কেনার এবং বেচার জন্য সেরা সময়ের জটিলতা বিশ্লেষণ

সময়ের জটিলতা

উপরের কোডটির সময় জটিলতা উপর) কারণ আমরা একবারে দামের অ্যারেটি অতিক্রম করছি। এখানে n দাম অ্যারের দৈর্ঘ্য।

স্থান জটিলতা

উপরের কোডটির স্পেস জটিলতা ও (1) কারণ আমরা কেবল উত্তর সঞ্চয় করতে মেমরি ব্যবহার করি।

তথ্যসূত্র