Mündəricat
Problem bəyanat
Birja LeetCode Həllini Almaq və Satmaq üçün Ən Yaxşı Vaxt – “Səhm almaq və satmaq üçün ən yaxşı vaxt” bildirir ki, Sizə qiymətlər sırası verilir, burada qiymətlər[i] verilmiş bir səhmin onuncu gündə qiymətidir.
Bir səhm almaq üçün bir gün seçərək və gələcəkdə həmin səhmi satmaq üçün başqa bir gün seçərək qazancınızı maksimuma çatdırmaq istəyirsiniz.
Bu əməliyyatdan əldə edə biləcəyiniz maksimum gəliri qaytarın. Heç bir qazanc əldə edə bilmirsinizsə, 0 qaytarın.
Misal:
prices = [7,1,5,3,6,4]
5
Explanation:
Siz 2-ci gündə (qiymət = 1) alıb, 5-ci gündə sata bilərsiniz (qiymət = 6), mənfəət = 6-1 = 5.
Qeyd etmək vacibdir ki, 2-ci gündə alış və 1-ci gündə satışa icazə verilmir, çünki satışdan əvvəl satın almalısınız.
prices = [7,6,4,3,1]
0
Explanation:
Bu vəziyyətdə heç bir əməliyyat baş vermir və maksimum mənfəət = 0.
Brute Force Həll
Idea:
Hər j-ci gün biz onu satıb-satmayacağımızı yoxlayacağıq, maksimum nə olacaq gəlir j-ci gündən əvvəl alsaq.
Kodu
Səhmlərin alınması və satışı üçün ən yaxşı vaxtın C++ proqramı:
#include <bits/stdc++.h>
using namespace std;
int maxProfit(vector<int> &prices)
{
int n = prices.size();
int answer = 0;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
answer = max(answer, prices[j] - prices[i]);
}
}
return answer;
}
int main()
{
vector<int> prices = {7, 1, 5, 3, 6, 4};
cout << maxProfit(prices) << endl;
return 0;
}
5
Səhm almaq və satmaq üçün ən yaxşı vaxtın JAVA proqramı:
public class TutorialCup
{
public static int maxProfit(int[] prices)
{
int n = prices.length;
int answer = 0;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
answer=Math.max(answer, prices[j] - prices[i]);
}
}
return answer;
}
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println(maxProfit(prices));
}
}
5
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
Yuxarıdakı kodun zaman mürəkkəbliyi O(N^2)-dir, çünki biz bütün kodlar üzərindən keçirik massiv cütləri.
Kosmik Mürəkkəblik
Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz heç bir əlavə yerdən istifadə etmirik.
Optimallaşdırılmış Həll
Idea:
Hər j-ci element üçün biz tapacağıq minimum element ondan əvvəl, belə ki, j-ci element üçün ən yaxşı cütü düzəldək.
Kodu
Səhmlərin alınması və satışı üçün ən yaxşı vaxtın C++ proqramı:
#include <bits/stdc++.h>
using namespace std;
int maxProfit(vector<int> &prices)
{
int answer = 0;
int mi = INT_MAX;
for (auto ele : prices)
{
answer = max(answer, ele - mi);
mi = min(mi, ele);
}
return answer;
}
int main()
{
vector<int> prices = {7, 1, 5, 3, 6, 4};
cout << maxProfit(prices) << endl;
return 0;
}
5
Səhm almaq və satmaq üçün ən yaxşı vaxtın JAVA proqramı:
public class TutorialCup
{
public static int maxProfit(int[] prices) {
int answer = 0;
int n=prices.length;
int mi = Integer.MAX_VALUE;
for (int i=0;i<n;i++)
{
answer = Math.max(answer, prices[i] - mi);
mi = Math.min(mi,prices[i]);
}
return answer;
}
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println(maxProfit(prices));
}
}
5
Üçün Mürəkkəblik Təhlili Səhmlər almaq və satmaq üçün ən yaxşı vaxt LeetCode Həlli
Zamanın mürəkkəbliyi
Yuxarıdakı kodun zaman mürəkkəbliyi O(N)-dir, çünki biz üzərindən keçirik array yalnız bir dəfə.
Kosmik Mürəkkəblik
Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki biz heç bir əlavə yerdən istifadə etmirik.
References: https://en.wikipedia.org/wiki/Brute-force_search
https://download.java.net/java/GA/jdk14/docs/api/java.base/java/lang/reflect/Array.html
