Най-доброто време за купуване и продажба на акции с решение за изчакване на Leetcode


Ниво на трудност M
Често задавани в Кирпич Амазонка Goldman Sachs Yahoo
Динамично програмиране

Изявление на проблема

В задачата „Най-доброто време за покупка и продажба на акции с Cooldown“ ни е даден масив, където всеки елемент в масива съдържа цената на дадената акция за този ден.

Няма ограничение за броя на транзакциите. Дефиницията на сделката е закупуване на една акция от акции и продажба на тази акция от акции.

Нашата задача е да намерим максималната печалба при следните ограничения:

  1. не можем да закупим нова акция, ако не сме продали предишната. тоест в даден момент можем да имаме най-много един запас.
  2. ако продадем акция на i-ия ден, тогава не можем да купим акции на (i + 1) -вия ден. Това е 1 ден период на изчакване

Пример

prices = [1,2,3,0,2]
3

Обяснение: максималната печалба, която може да бъде получена, е 3. Следват подробностите за сделката:

Първи ден: купете

Втори ден: продавам

Трети ден: охлаждане

Четвърти ден: купувайте

Пети ден: продавам

Подход за най-доброто време за покупка и продажба на акции с решение за изчакване на Leetcode

За да разрешим този проблем, трябва да отбележим няколко неща:

  1. Винаги, когато искаме да продадем акция, трябва да сме я закупили по-рано. Средството за продажба на акция зависи от закупуването на акция.
  2. Един ден от периода на изчакване е задължителен. Така че закупуването на акция зависи от периода на възстановяване.

Имайки предвид тези точки, можем да дефинираме състоянията:

  • ДЪРЖАВА-А: В това състояние можем или да си купим акция, или просто да си починем.
  • СЪСТОЯНИЕ-Б: След закупуване на акция можем или да продадем акцията, или просто да вземем останалото.
  • STATE-C: Това е състояние на изчакване. След изтичане на периода на изчакване преминаваме към STATE-A.

Най-доброто време за покупка и продажба на акции с Cooldown

Връзката между тези три състояния може да бъде превърната в алгебричен израз където STATE-X [i] представлява максималната печалба до i-ия ден в състояние x.

sa->STATE-A,sb->STATE-B,sc->STATE-C
 sa[i]=max(sa[i-1],sc[i-1]);
 sb[i]=max(sb[i-1],sa[i-1]-prices[i]);
 sc[i]=sb[i-1]+prices[i];

След n итерация, максималната печалба ще бъде max (sa [n-1], sc [n-1]), тъй като, тъй като искаме да увеличим печалбата, така че в крайна сметка няма да купуваме акции и да не ги продаваме.

Основни случаи:

sa[0]=0;
sb[0]=-prices[0]
sc[0]=INT_MIN

изпълнение

C ++ код за най-доброто време за купуване и продажба на акции с Cooldown

#include <bits/stdc++.h> 
using namespace std; 
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n<1)return 0;
       int sa[n],sb[n],sc[n];
        sa[0]=0,sb[0]=-prices[0],sc[0]=INT_MIN;
        for(int i=1;i<n;i++)
        {
            sa[i]=max(sa[i-1],sc[i-1]);
            sb[i]=max(sb[i-1],sa[i-1]-prices[i]);
            sc[i]=sb[i-1]+prices[i];
        }
        return max(sa[n-1],sc[n-1]);  
    }
int main() 
{ 
 vector<int> arr = { 1,2,3,0,2 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
3

Java код за най-доброто време за купуване и продажба на акции с Cooldown

import java.util.Arrays; 
public class Tutorialcup {
    public static int  maxProfit(int[] prices) {
          int n=prices.length;
    if(n<1)return 0;
    int[] sa = new int[n];
    int[] sb = new int[n];
    int[] sc = new int[n];
    sa[0] = 0;sb[0] = -prices[0]; sc[0] = Integer.MIN_VALUE;

    for (int i = 1; i < n; ++i) {
      sa[i] = Math.max(sa[i-1],sc[i-1]);
      sb[i] = Math.max(sb[i-1],sa[i-1]-prices[i]);
      sc[i] = sb[i-1]+prices[i];
    }

    return Math.max(sa[n-1],sc[n-1]);  
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,0,2}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
3

Анализ на сложността на най-доброто време за купуване и продажба на акции с разтвор за изчакване на Leetcode

Времева сложност

Сложността във времето на горния код е О (п) защото обхождаме ценовия масив само веднъж. Тук n е дължината на ценовия масив.

Космическа сложност

Сложността на пространството на горния код е О (п) защото използваме масив за съхраняване на информация за различни състояния.

Препратки