Лепшы час для пакупкі і продажу рашэння Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка DE Шоу facebook Microsoft Morgan Stanley Uber
масіў Прагны

Пастаноўка праблемы

У задачы "Лепшы час куплі і продажу акцый II" нам даецца масіў, дзе кожны элемент масіва ўтрымлівае цану дадзенай акцыі ў той дзень.

Вызначэнне здзелка купляе адну акцыю і прадае адну акцыю.

Наша задача знайсці максімальны прыбытак пры наступных абмежаваннях:

  1. мы не можам купіць новую акцыю, калі не прадалі папярэднюю. гэта значыць, у той час мы можам мець не больш за адзін запас.
  2. мы можам рабіць колькі заўгодна транзакцый.

Прыклад

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

Тлумачэнне: максімальны прыбытак, які можна атрымаць, складае 7. Далей прыводзіцца дэталь транзакцыі:

Першы дзень: адпачынак

Другі дзень: купляйце

Трэці дзень: прадаць

Чацвёрты дзень: купляйце

Пяты дзень: прадаць

Шосты дзень: адпачынак

Падыход да лепшага часу для пакупкі і продажу рашэння Leetcode

Паколькі ў нас няма абмежаванняў па колькасці транзакцый, мы падумаем пра алчны алгарытм тут. Такім чынам, кожны раз мы будзем купляць акцыі па мінімальнай цане і прадаваць па максімальнай цане. Мы можам падсумаваць гэта так, што пры кожным мінімуме мы будзем купляць акцыі, а пры кожным мінімуме мы будзем прадаваць акцыі. Гэта тлумачыцца на малюнку, прыведзеным ніжэй. Гэта графік паміж цаной акцый і днямі. рашэнне леткода для лепшага часу для пакупкі і продажу акцый II

Мы можам зрабіць гэта прасцей, калі заўважым, што максімумы ўтвараюцца пры даданні да мінімумаў невялікіх значэнняў. Такім чынам, нягледзячы на ​​адсочванне ўсіх мінімумаў і максімумаў для вылічэння максімальнай прыбытку, мы можам непасрэдна дадаць тыя значэнні да нашай прыбытку, для якіх мы знайшлі станоўчы нахіл, гэта цэны [i]> цэны [i-1]. Даданне ўсіх такіх значэнняў дасць нам максімальны прыбытак.

рашэнне леткода для лепшага часу для пакупкі і продажу акцый II

Рэалізацыя

Код C ++ для лепшага часу куплі і продажу акцый II

#include <bits/stdc++.h> 
using namespace std; 
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
int main() 
{ 
 vector<int> arr = { 7,1,5,3,6,4 }; 
 cout<<maxProfit(arr)<<endl; 
 return 0;
}
7

Код Java для лепшага часу для пакупкі і продажу акцый II

import java.util.Arrays; 
public class Tutorialcup {
     public static int maxProfit(int[] prices) {
        int ans = 0;
        int n=prices.length;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
  public static void main(String[] args) {
    int [] arr = {7,1,5,3,6,4}; 
    int ans=  maxProfit(arr);
    System.out.println(ans);
  }
}
7

Аналіз складанасці лепшага часу для пакупкі і продажу акцый II з рашэннем Leetcode

Часовая складанасць

Часавая складанасць вышэйзгаданага кода Аб (п) таму што мы праходзім масіў цэн толькі адзін раз. Тут n - даўжыня цэнавага масіва.

Касмічная складанасць

Касмічная складанасць вышэйзгаданага кода складаецца ў O (1) таму што мы выкарыстоўваем памяць толькі для захоўвання адказу.

Спасылкі