ເວລາທີ່ດີທີ່ສຸດທີ່ຈະຊື້ແລະຂາຍຫຸ້ນ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance Cisco DE Shaw eBay Expedia ເຟສບຸກ Goldman Sachs ກູໂກ JP Morgan Microsoft Morgan Stanley Oracle PayPal Qualtrics Samsung VMware
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ຖະແຫຼງການບັນຫາ  

ບັນຫາ“ ເວລາທີ່ດີທີ່ສຸດທີ່ຈະຊື້ແລະຂາຍຫຸ້ນ” ລະບຸວ່າທ່ານຖືກມອບໃຫ້ array ລາຄາຂອງຄວາມຍາວ n, ເຊິ່ງອົງປະກອບຂອງມັນຈະຮັກສາລາຄາຫຸ້ນໃນມື້ ໜຶ່ງ.
ຖ້າພວກເຮົາສາມາດເຮັດທຸລະ ກຳ ໄດ້ພຽງແຕ່ຄັ້ງດຽວເທົ່ານັ້ນ, ນັ້ນກໍ່ຄືການຊື້ໃນມື້ ໜຶ່ງ ແລະຂາຍໃນມື້ອື່ນທີ່ ກຳ ລັງຈະມາເຖິງ, ມັນຈະເປັນ ກຳ ໄລສູງສຸດທີ່ຫາໄດ້ມາແນວໃດ.

ຍົກຕົວຢ່າງ  

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

ລະບົບວິເຄາະ  

ຖ້າພວກເຮົາຊື້ຫຸ້ນໃນມື້ ໜຶ່ງ, ກຳ ໄລສູງສຸດແມ່ນໄດ້ມາຈາກການຂາຍຫຸ້ນໃນມື້ລະຫວ່າງ i + 1 ເຖິງ n, ເຊັ່ນວ່າມື້ນັ້ນມີລາຄາສູງສຸດຂອງຫຼັກຊັບແລະນັ້ນແມ່ນໃຫຍ່ກວ່າລາຄາ [i].
ພິຈາລະນາລາຄາ = {7, 1, 5, 3, 6, 4}

ເວລາທີ່ດີທີ່ສຸດທີ່ຈະຊື້ແລະຂາຍຫຸ້ນPin
ສະນັ້ນ, ກຳ ໄລສູງສຸດແມ່ນໄດ້ມາຈາກການຊື້ຫຸ້ນໃນວັນທີ 2 ແລະຂາຍມັນໃນວັນທີ 5, ກຳ ໄລສູງສຸດທີ່ຫາໄດ້ແມ່ນ 5.

ວິທີການ Naive ສໍາລັບເວລາທີ່ດີທີ່ສຸດໃນການຊື້ແລະຂາຍຫຸ້ນ  

ວິທີການທີ່ໂງ່ຈ້າໃນການຈັດຕັ້ງປະຕິບັດວິທີການຂ້າງເທິງນີ້ແມ່ນການ ດຳ ເນີນການສອງວົງແຫວນທີ່ມີຮັງ, ໜຶ່ງ ສຳ ລັບມື້ຊື້ແລະອີກວິທີ ໜຶ່ງ ເພື່ອຊອກຫາ ກຳ ໄລສູງສຸດໃນວັນຂ້າງ ໜ້າ.

ເບິ່ງ
ກວດເບິ່ງວ່າ Array ມີສ່ວນປະກອບທີ່ຕິດພັນກັບສິ່ງທີ່ຊ້ ຳ ຊ້ອນອະນຸຍາດ

ລະຫັດ Pseudo

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), ເພາະວ່າພວກເຮົາ ກຳ ລັງໃຊ້ວົງແຫວນຮັງສອງອັນ ສຳ ລັບເກັບມື້ເພື່ອຊື້ແລະຂາຍຫຸ້ນ. ດັ່ງນັ້ນຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນ poltnomial.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (1), ເນື່ອງຈາກວ່າພວກເຮົາບໍ່ storign ຂໍ້ມູນໃດໆກ່ຽວກັບແຕ່ລະອົງປະກອບໃນໂຄງສ້າງຂໍ້ມູນໃດໆ. ພວກເຮົາໄດ້ໃຊ້ພື້ນທີ່ຄົງທີ່ເທົ່ານັ້ນ. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນເປັນເສັ້ນ.
ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບທີ່ຢູ່ໃນຂບວນ.

ວິທີການທີ່ດີທີ່ສຸດ ສຳ ລັບເວລາທີ່ດີທີ່ສຸດໃນການຊື້ແລະຂາຍຫຸ້ນ  

ວິທີການທີ່ດີກວ່າແມ່ນການປະກອບແບບ array ອົງປະກອບທີ່ມີຄ່າສູງສຸດໃນປະຈຸບັນ ລາ​ຄາ array ຈາກ index i + 1 ເຖິງ n. ນັ້ນແມ່ນ, ພວກເຮົາ ກຳ ລັງໃຫ້ຄວາມ ສຳ ຄັນກັບວຽກທີ່ເຮັດໂດຍວົງຮັງພາຍໃນແບບບໍ່ມີຕົວຕົນ. ດັ່ງນັ້ນ, ພວກເຮົາສາມາດທົດແທນວົງຈອນຮັງພາຍໃນໂດຍການຊອກຫາສູງສຸດໂດຍກົງ. ສູດການຄິດໄລ່ precomputation ເຮັດວຽກໃນລັກສະນະດັ່ງຕໍ່ໄປນີ້.

  1. ສ້າງຂບວນທີ່ມີຊື່ວ່າ maxSP ຂອງຂະ ໜາດ ເທົ່າກັບຂະ ໜາດ ຂອງ ລາ​ຄາ array ແລະ max ຕົວແປແລະເລີ່ມຕົ້ນມັນເປັນຄ່າຕ່ ຳ ສຸດ.
  2. ເລີ່ມຕົ້ນຈາກດັດຊະນີສຸດທ້າຍໃນ ລາ​ຄາ ຂບວນ.
    1. ຖ້າລາຄາ [i] ສູງກວ່າສູງສຸດ
      1. ປັບປຸງສູງສຸດເປັນລາຄາ [i] ແລະເຮັດໃຫ້ maxSP [i] ເປັນຄ່າຕ່ ຳ ສຸດ
    2. ອື່ນຖ້າລາຄາ [i] ບໍ່ສູງກວ່າສູງສຸດ
      1. ປັບປຸງ maxSP [i] = ສູງສຸດ.
  3. ຫຼັງຈາກການ ຄຳ ນວນກ່ອນ, ພວກເຮົາປະຕິບັດຕາມວິທີການທີ່ບໍ່ມີຕົວຕົນແລະທົດແທນວົງແຫວນພາຍໃນໂດຍການ ນຳ ໃຊ້ອາໄລ່ maxSP ທີ່ພວກເຮົາຫາກໍ່ສ້າງ.
ເບິ່ງ
ອົງປະກອບທີ່ມັກໃນ Array

ລະຫັດ Pseudo

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

ລະຫັດ

ລະຫັດ Java ສຳ ລັບເວລາທີ່ດີທີ່ສຸດໃນການຊື້ແລະຂາຍບັນຫາຫຸ້ນ

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 ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບທີ່ຢູ່ໃນຂບວນ.