አክሲዮን ለመግዛት እና ለመሸጥ ምርጥ ጊዜ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን ፓም ብሉምበርግ ByteDance Cisco ዴ ሻው eBay Expedia ፌስቡክ ጎልድማን ሳክስ google ጂፒ ሞርጋን የ Microsoft ሞርጋን ስታንሊ በ Oracle የ PayPal Qualtrics ሳምሰንግ VMware
ሰልፍ ተለዋዋጭ ፕሮግራም

የችግሩ መግለጫ

ችግሩ “አክሲዮን ለመግዛት እና ለመሸጥ የተሻለው ጊዜ” አንድ እንደተሰጠዎት ይናገራል ደርድር የርዝመት n ዋጋዎች ፣ የአይነቱ ንጥረ ነገር በእለት ቀን የአክሲዮን ዋጋን የሚያከማችበት።
አንድ ግብይት ብቻ ማድረግ ከቻልን ማለትም ፣ በአንድ ቀን ለመግዛት እና በሚቀጥለው መጪው ቀን ለመሸጥ ፣ የተገኘው ከፍተኛ ትርፍ ምን ይሆናል ፡፡

ለምሳሌ

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

አልጎሪዝም

በአክሲዮን ቀን ላይ አክሲዮኑን ከገዛን ከፍተኛው ትርፍ የሚገኘው በ + + 1 እስከ n መካከል ባለው ቀን ውስጥ አክሲዮኑን በመሸጥ ነው ፣ ይህም ቀን ከፍተኛው የአክሲዮን ዋጋ ያለው እና ከዚያ ዋጋ [i] የሚበልጥ ነው።
ዋጋዎችን ያስቡ = {7, 1, 5, 3, 6, 4}

አክሲዮን ለመግዛት እና ለመሸጥ ምርጥ ጊዜ
ስለዚህ ከፍተኛው ትርፍ የሚገኘው በቀን 2 ቀን አክሲዮን በመግዛት እና በ 5 ቀን በመሸጥ ሲሆን የተገኘው ከፍተኛ ትርፍ 5 ነው ፡፡

አክሲዮን ለመግዛት እና ለመሸጥ ለምርጥ ጊዜ የዋህ አቀራረብ

ከላይ የተጠቀሰውን ስልተ-ቀመር ተግባራዊ ለማድረግ የዋህነት አቀራረብ ሁለት የጎጆ ቀለበቶችን ማካሄድ ነው ፣ አንዱ ለግዢ ቀን እና በመጪዎቹ ቀናት ከፍተኛውን ትርፍ ለማግኘት ፡፡

የውሸት ኮድ

int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = price[i];
  int max = -infinity;
  // Finding the maximum stock price greater than costPrice on upcoming days
  for (int j = i + 1; j < n; j++) {
    if (prices[j] > costPrice) {
      max = maximum(max, a[j]);
    }
  }
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n ^ 2) ፣ አክሲዮን ለመግዛት እና ለመሸጥ ቀኑን ለመምረጥ ሁለት የጎጆ ቀለበቶችን እየተጠቀምን ስለሆነ ፡፡ ስለዚህ የጊዜ ውስብስብነት ጊዜያዊ ነው።

የቦታ ውስብስብነት

ኦ (1) ፣ እኛ በማንኛውም የውሂብ መዋቅር ውስጥ እያንዳንዱን ንጥረ ነገር በተመለከተ ማንኛውንም መረጃ አናስገባም ፡፡ የምንጠቀምበት ቋሚ ቦታ ብቻ ነው ፡፡ ስለዚህ የቦታ ውስብስብነት መስመራዊ ነው።
በሰልፍ ውስጥ የንጥሎች ብዛት የት ነው።

አክሲዮን ለመግዛት እና ለመሸጥ ለተሻለ ጊዜ ጥሩ አቀራረብ

የተሻለ አካሄድ አንድን ማቋቋም ነው ደርድር በውስጡ ያለው ንጥረ ነገር ከፍተኛውን እሴት በ ውስጥ ያከማቻል ዋጋዎች ድርድር ከ ማውጫ i + 1 እስከ n። ማለትም ፣ በውስጣችን በተጠለፈ ሉፕ በተሰራው የተሳሳተ አካሄድ የተሰራውን ሥራ ቀድመን እየቆጠርን ነው ፡፡ ስለዚህ ፣ ከፍተኛውን በቀጥታ በማግኘት የውስጠኛውን የጎጆ ጥብጣብ መተካት እንችላለን ፡፡ የቅድመ-ማስላት ስልተ ቀመር በሚከተለው መንገድ ይሠራል።

  1. መጠኑ እኩል የሆነ መጠን maxSP የተሰየመ ድርድር ይፍጠሩ ዋጋዎች ድርድር እና ተለዋዋጭ ከፍተኛ እና እንደ ዝቅተኛ እሴት ያስጀምሩት።
  2. በ ውስጥ ካለፈው መረጃ ጠቋሚ ይጀምሩ ዋጋዎች ድርድር
    1. ዋጋዎች [i] ከከፍተኛው የሚበልጥ ከሆነ
      1. ከፍተኛውን እንደ ዋጋዎች ያዘምኑ እና እኔ maxSP [i] ን እንደ ዝቅተኛ እሴት ያድርጉ
    2. ሌሎች ዋጋዎች [i] ከከፍተኛው የማይበልጥ ከሆነ
      1. MaxSP ን ያዘምኑ [i] = ከፍተኛ።
  3. ከቅድመ ስሌቱ በኋላ የዋህነት አካሄድን እንከተላለን እናም አሁን የፈጠርነውን ከፍተኛውን የ “maxSP” ድርድር በመጠቀም የውስጠኛውን የጎጆውን ሉፕ እንተካለን ፡፡

የውሸት ኮድ

// Pre computation
int max = -infinity;
for (int i = n - 1; i >= 0; i--) {
  if (prices[i] > max) {
    max = prices[i];
    maxSP[i] = -infinity;
  } else {
    maxSP[i] = max;
  }
}
// Do as in naive approach
int maxProfit = -infinity;
for (int i = 0; i < n; i++) {
  int costPrice = prices[i];
  // Rather than using a loop to calculate max, we can directly get it from maxSP array
  int max = maxSP[i];
  int profit = 0;
  if (max != -infinity) {
    profit = max - costPrice;
  }
  maxProfit = maximum(maxProfit, profit);
}

ኮድ

የጃቫ ኮድ የአክሲዮን ችግርን ለመግዛት እና ለመሸጥ ለተሻለ ጊዜ

import java.util.Scanner;

class BestTimetoBuyandSellStock {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // Prices array
        int prices[] = new int[]{7, 1, 5, 3, 6, 4};

        // Calculating the max profit
        int ans = maxProfit(prices, prices.length);

        // Print the answer
        System.out.println(ans);
    }

    private static int maxProfit(int[] prices, int n) {
        int maxSP[] = new int[n];
        int max = Integer.MIN_VALUE;

        // Construct the maxSP array
        for (int i = n - 1; i >= 0; i--) {
            if (prices[i] > max) {
                max = prices[i];
                maxSP[i] = Integer.MIN_VALUE;
            } else {
                maxSP[i] = max;
            }
        }

        int profit = 0;
        for (int i = 0; i < n; i++) {
            if (maxSP[i] != Integer.MIN_VALUE) {
                profit = Math.max(profit, maxSP[i] - prices[i]);
            }
        }

        // Return profit
        return profit;
    }
}
5

የአክሲዮን ችግርን ለመግዛት እና ለመሸጥ ለተሻለ ጊዜ C ++ ኮድ

#include <bits/stdc++.h>
using namespace std;

int maxProfit(int *prices, int n) {
    int maxSP[n];
    int max = INT_MIN;
    
    // Construct the maxSP array
    for (int i = n - 1; i >= 0; i--) {
        if (prices[i] > max) {
            max = prices[i];
            maxSP[i] = INT_MIN;
        } else {
            maxSP[i] = max;
        }
    }
    
    int profit = 0;
    for (int i = 0; i < n; i++) {
        if (maxSP[i] != INT_MIN) {
            profit = std::max(profit, maxSP[i] - prices[i]);
        }
    }
    
    // Return profit
    return profit;
}

int main() {
    // Prices array
    int prices[] = {7, 1, 5, 3, 6, 4};
    
    // Calculating the max profit
    int ans = maxProfit(prices, sizeof(prices) / sizeof(prices[0]));
    
    // Print the answer
    cout<<ans<<endl;
    return 0;
}
5

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n) ፣ የከፍተኛው ትርፍ ስሌት እና ስሌት ወቅት ከድርድሩ n ንጥረ ነገሮች በላይ እንደተጓዝን። የጊዜ ውስብስብነቱ መስመራዊ ነው ፡፡

የቦታ ውስብስብነት

ኦ (n) ፣ ምክንያቱም በቅድመ ክፍያ ሂሳብ ወቅት ከፍተኛውን የሽያጭ ዋጋ ከአሁኑ ቀን በኋላ በአንድ ቀን ውስጥ እናከማች ነበር ፡፡ በድርድሩ ውስጥ ላሉት ሁሉም ንጥረ ነገሮች የተከማቸ ስለሆነ። የቦታ ውስብስብነት እንዲሁ መስመራዊ ነው።
በሰልፍ ውስጥ የንጥሎች ብዛት የት ነው።