ពេលវេលាល្អបំផុតដើម្បីទិញនិងលក់ភាគហ៊ុន


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ByteDance ស៊ីស្កូ ឌីសៅ របស់ eBay Expedia Facebook ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន google ដោយឡែកក្រុមហ៊ុន JP Morgan ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Morgan Stanley ក្រុមហ៊ុន Oracle បានតាមរយៈការ Qualtrics ក្រុមហ៊ុន Samsung VMware
អារេ ការសរសេរកម្មវិធីឌីណាមិក

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា "ពេលវេលាល្អបំផុតក្នុងការទិញនិងលក់ភាគហ៊ុន" បញ្ជាក់ថាអ្នកត្រូវបានផ្តល់ឱ្យ អារេ នៃតម្លៃនៃប្រវែង n ដែលជាកន្លែងដែលធាតុអ៊ីសផ្ទុកតម្លៃភាគហ៊ុននៅថ្ងៃមួយថ្ងៃ។
ប្រសិនបើយើងអាចធ្វើប្រតិបត្តិការតែមួយបាននោះគឺទិញនៅថ្ងៃណាមួយហើយលក់នៅថ្ងៃខាងមុខទៀតតើនឹងទទួលបានប្រាក់ចំណេញអតិបរមាដែលរកបាន។

ឧទាហរណ៍

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

ក្បួនដោះស្រាយ

ប្រសិនបើយើងទិញភាគហ៊ុននៅថ្ងៃមួយប្រាក់ចំណេញអតិបរិមាត្រូវបានរកបានដោយការលក់ភាគហ៊ុននៅចន្លោះថ្ងៃរវាង i + 1 ដល់ n ដូចជាថ្ងៃនោះមានតម្លៃខ្ពស់បំផុតនៃភាគហ៊ុនហើយនោះគឺធំជាងតម្លៃ [i] ។
ពិចារណាលើតម្លៃ = {៧, ១, ៥, ៣, ៦, ៤}

ពេលវេលាល្អបំផុតដើម្បីទិញនិងលក់ភាគហ៊ុន
ដូច្នេះប្រាក់ចំណេញអតិបរមាត្រូវរកបានដោយការទិញភាគហ៊ុននៅថ្ងៃទី ២ ហើយលក់វានៅថ្ងៃទី ៥ ប្រាក់ចំណេញអតិបរមាដែលទទួលបានគឺ ៥ ។

វិធីសាស្រ្តណាណូសម្រាប់ពេលវេលាល្អបំផុតដើម្បីទិញនិងលក់ភាគហ៊ុន

វិធីឆោតល្ងង់ដើម្បីអនុវត្តក្បួនដោះស្រាយខាងលើគឺត្រូវដំណើរការរង្វិលជុំដែលមានសំបុកពីរគឺមួយសម្រាប់ថ្ងៃទិញនិងមួយទៀតរកប្រាក់ចំណេញអតិបរមានៅថ្ងៃខាងមុខ។

កូដផូដាដូ

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);
}

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (n ^ 2), ពីព្រោះយើងកំពុងប្រើរង្វិលជុំដែលមានពីរសម្រាប់ជ្រើសរើសថ្ងៃដើម្បីទិញនិងលក់ភាគហ៊ុន។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាគឺមានរាងប៉ូល។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១), ដោយសារយើងមិនមានព័ត៌មានទាក់ទងនឹងធាតុនីមួយៗនៅក្នុងរចនាសម្ព័ន្ធទិន្នន័យណាមួយ។ យើងបានប្រើចន្លោះថេរប៉ុណ្ណោះ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺជាលីនេអ៊ែរ។
ដែល n ជាចំនួនធាតុនៅក្នុងអារេ។

វិធីសាស្រ្តល្អប្រសើរបំផុតសម្រាប់ពេលវេលាល្អបំផុតដើម្បីទិញនិងលក់ភាគហ៊ុន

វិធីសាស្រ្តល្អប្រសើរជាងមុនគឺត្រូវបង្កើត អារេ ធាតុអ៊ីដ្រូតផ្ទុកតម្លៃអតិបរមាដែលមាននៅក្នុង តម្លៃ ជួរពីសន្ទស្សន៍អាយ + ១ ដល់ n ។ នោះគឺយើងកំពុងបញ្ចូលកិច្ចការដែលបានធ្វើដោយរង្វិលជុំខាងក្នុងនៃរាងសំប៉ែត។ ដូច្នេះនោះយើងអាចជំនួសរង្វិលជុំខាងក្នុងដោយរកឃើញចំនួនអតិបរមា។ ក្បួនដោះស្រាយបុព្វហេតុធ្វើការតាមរបៀបដូចខាងក្រោម។

  1. បង្កើតអារេដែលមានឈ្មោះថា maxSP នៃទំហំស្មើនឹងទំហំរបស់ តម្លៃ អារេនិងអថេរអតិបរមាហើយចាប់ផ្តើមវាជាតម្លៃអប្បបរមា។
  2. ចាប់ផ្តើមពីសន្ទស្សន៍ចុងក្រោយនៅក្នុង តម្លៃ អារេ។
    1. ប្រសិនបើតម្លៃ [ខ្ញុំ] ធំជាងអតិបរិមា
      1. ធ្វើបច្ចុប្បន្នភាពអតិបរិមាជាតំលៃ [i] និងធ្វើអោយ maxSP [i] ជាតម្លៃអប្បបរមា
    2. ម៉្យាងទៀតប្រសិនបើតម្លៃ [i] មិនធំជាងតម្លៃអតិបរិមា
      1. ធ្វើបច្ចុប្បន្នភាព maxSP [i] = អតិបរមា។
  3. បន្ទាប់ពីការគណនាមុនយើងធ្វើតាមវិធីឆោតល្ងង់ហើយជំនួសរង្វិលជុំដែលដាក់ក្នុងផ្នែកខាងក្នុងដោយប្រើអារេអិចអេសភីដែលយើងទើបតែបង្កើត។

កូដផូដាដូ

// 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 នៃអារេក្នុងកំឡុងពេល precomputation និងការគណនានៃប្រាក់ចំណេញអតិបរមា។ ភាពស្មុគស្មាញនៃពេលវេលាគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

អូ (n), ពីព្រោះក្នុងកំឡុងពេលដែលយើងត្រូវរក្សាសិទ្ធិមុនយើងកំពុងរក្សាទុកថ្លៃលក់អតិបរមានៅមួយថ្ងៃបន្ទាប់ពីថ្ងៃបច្ចុប្បន្ន។ ចាប់តាំងពីវាត្រូវបានរក្សាទុកសម្រាប់ធាតុទាំងអស់នៅក្នុងអារេ។ ភាពស្មុគស្មាញនៃអវកាសក៏ជាលីនេអ៊ែរផងដែរ។
ដែល n ជាចំនួនធាតុនៅក្នុងអារេ។